Metric based resolvability of cycle related graphs

1.   Introduction, literature and basics

The seminal paper for the idea of a resolving set was written by Slater ^[28], and named the resolving set as the locating set where the locating set resolves all the vertices of a graph. Independently, Harary and Melter ^[6] revealed the idea of a location number and used the term metric dimension. In 2008, Hernando et al. generalized the idea of resolving sets by defining the fault-tolerant resolving set ^[7]. Later, Kelenc et al. in ^[9], defined a parameter referred to as the edge metric dimension, where the resolving set distinguishes any two edges of the graph instead of vertices.

After the introduction of resolving parameters, considerable work has been done concerning its applications and many theoretical properties. For instance, its applications include pharmaceutical chemistry ^[4], image processing ^[16], the coin weighing problem ^[30], computer networks ^[15], combinatorial optimizations ^[27], robot navigations ^[10], the facility location problem, and sonar and coastguard LORAN ^[28]; for further details, see ^[19,20].

Similarly, regarding the theoretical investigations of the resolvability parameter, various results have been found and extensively studied in the literature, which has highly contributed to understanding this parameter's mathematical properties associated with distances in graphs. For example, products of graphs ^[3,26], strong metric dimension of power graphs ^[14], fault tolerance of convex polytopes ^[25], and the edge metric dimension operated graph ^[21]. The complexity of these concepts, which is NP-complete, was proved in ^[9,12].

For the latest results on metric dimension, see ^[17,18]. The researchers in ^[1,11,33] studied the edge metric dimension of polytopes and the barycentric subdivision of Cayley graphs, chemical networks can be found in ^[31], a comparative study can be seen in ^[22], and for more detail on this concept, see ^[32].

The latest literature on the fault-tolerant version of metric dimension for path, interconnection networks, different graph's bounds and some applications of this concept are available in ^[8,24]. Recent work on chemical structures linked to this concept are studied in ^[2,17,23,29].

Kelenc et al. ^[9] asked the question about the relation among resolvability parameters of a graph. Motivated by this question in this paper, we study the metric, edge metric, and fault-tolerant resolvability parameter of the convex polytope $F_{♃}$ and give relations among these parameters by finding their exact values.

Now, we give the formal definitions of distance based concepts of graph theory used in this work.

Consider a graph $G$ without multiple edges with vertex set $V(G)$ and edge set $E(G).$ The distance between a pair of vertices $a_1$ and $a_2$ is the length of the smallest path, represented by $d(a_1, a_2).$ A vertex $v\in V(G)$ differentiates a pair $a_1$ and $a_2$ if $d(v, a_1)\neq d(v, a_2).$ A set $B\subset V(G)$ is called a basis set/resolving set of $G$ if any two distinct vertices of $G$ are distinguished by any vertex of $B.$ A resolving set of minimum cardinality is named the basis, and the number of vertices in it is the metric dimension of $G,$ denoted by $dim(G).$ The distance between a vertex $u\in V(G)$ and an edge $e = a_1a_2\in E(G)$ is defined as $d(e, v) = \min\{d(a_1, v), d(a_2, v)\}$. A vertex $x$ in the graph $G$ is said to divide two edges $e_1$ and $e_2$ in $G$ if the distance between $x$ and $e_1$ is not equal to the distance between $x$ and $e_2$. A subset $B_e$ of the vertices of a graph $G$ is considered an edge resolving set if every pair of edges in $G$ is separated by at least one vertex in $B_e$. The edge metric dimension of a graph, denoted by $dim_e(G)$, refers to the smallest number of vertices in a set that can uniquely determine the edges of the graph.

A resolving set $B_f$ of a graph $G$ is a fault-tolerant resolving set if for each $v\in B_f$ the set $B_f\backslash\{v\}$ remains a resolving set for $G,$ and the minimum number of elements in $B_f(G)$ is called the fault-tolerant metric dimension, denoted by $dim_f(G).$

Observation 1.1. ^[13] Consider a simple connected graph $G$ with dimension $2$. Let $\{{a}_1, {a}_2\}\subset V(G)$ be a metric basis of $G$. In this case, both ${a}_1$ and ${a}_2$ have a degree of at most $3$, and there is only one shortest path between them.

Observation 1.2. ^[5] Let $dim(G)$ and $dim_f(G)$ denote the metric dimension and fault-tolerant metric dimension of graph $G$, respectively. Subsequently,

2.   Convex polytope ${F}_{♃}$

Let ${F}_{♃}$ be a convex polytope graph. The vertex set of ${F}_{♃}$ is $V\left({F}_{♃}\right) = \{{a}_{☿}, \ {b}_{☿}, \ {c}_{☿}\ :{☿} = 1, 2, \dots, {♃}\}$, the edge set $E\left({F}_{♃}\right) = \{{a}_{☿}{a}_{{☿}+1}, \ {a}_{☿}{b}_{☿}, \ {a}_{{☿}+1}{b}_{☿}, \ {b}_{☿}{c}_{☿}, \ {b}_{☿}{c}_{{☿}+1}, \ {c}_{☿}{c}_{{☿}+1}\ :{☿} = 1, 2, \dots, n\}$, and $(.)_{{♃}+1} = (.)_1.$ The order and size of ${F}_{♃}$ is $3{♃}$, and $6{♃}$ respectively. The convex polytope ${F}_{♃}$ has one ${♃}$-face, $2{♃}$ $3$-face, and ${♃}$ $4$-face. Moreover, clearer visualization of the convex polytope ${F}_{♃}$ is in Figure 1 with a generalized labeling of vertices.

3.   Results on the convex polytope ${F}_{♃}$

Here you can find the outcomes of the metric dimension as well as its fault-tolerant extensions and the edge metric dimension. All the other theorems are based on the first theorem.

Theorem 3.1. Let ${F}_{♃}$ be a convex polytope graph with ${♃}\geq4.$ Then, the metric dimension of ${F}_{♃}$ is $3.$

Proof. To check the resolvability of graph ${F}_{♃},$ the proof has been divided into two sections:

Case 1: When ${♃}$ is even.

Consider the basis set $B = \{{a}_1, {a}_2, {a}_{\frac{{♃}+2}{2}}\}.$ The corresponding vector illustrations are

The inner cycle vertex positions with respect to the locating set $B$ are

The interior vertex positions with respect to the locating set $B$ are

The outer cycle vertex position with respect to the locating set $B$ are

Case 2: When ${♃}$ is odd.

The basis set for this case is $B = \{{a}_1, {a}_2, {a}_{\frac{{♃}+1}{2}}\}.$ The corresponding vector illustrations are

The inner cycle vertex positions with respect to the locating set $B$ are

The interior vertex positions with respect to the locating set $B$ are

The outer cycle vertex positions with respect to the locating set $B$ are

Since the vector representations in Eqs (3.1) and (3.2) of all vertices of ${F}_{♃}$ are different, it follows that $dim\left({F}_{♃}\right)\leq3.$

To establish the inverse inequality $dim\left({F}{♃}\right)\geq3,$ it is evident from Observation 1.1 that $dim\left({F}{♃}\right) = 2$ is not possible. According to the Observation, the vertices considered as candidates for the metric basis must have a maximum degree of three. Since ${F}_{♃}$ is a four-regular graph, it follows that $dim\left({F}_{♃}\right)\geq3$. Therefore, we can conclude that

□

Theorem 3.2. Suppose ${F}_{♃}$ be a convex polytope graph with ${♃}\geq4.$ The fault-tolerant metric dimension of ${F}_{♃}$ is precisely $4$.

Proof. To prove $dim_f\left({F}_{♃}\right)\leq4$, we split the proof into following two cases:

Case 1: ${♃}$ is even.

To prove $dim_f\left({F}_{♃}\right)\leq4$, consider the fault-tolerant basis set $B_f = \{{a}_1, {a}_\frac{♃}{2}, {c}_1, {c}_{\frac{♃}{2}}\}.$ The interactive depictions of for the vertices of graph are

The inner cycle vertex positions with respect to the fault-tolerant basis set $B_f$ are

The interior vertex positions with respect to the fault-tolerant basis set $B_f$ are

The outer cycle vertex positions with respect to the fault-tolerant basis set $B_f$ are

It is clear to see that the representations of all vertices in Eq (3.3) with respect to the fault-tolerant metric basis set $B_f$ are different, and thus it is proved that $dim_f\left({F}_{♃}\right)\leq4.$

From Theorem 3.1, and Observation 1.2, we directly obtain the converse, which concluded that

Case 2: ${♃}$ is odd.

To prove that $dim_f\left({F}_{♃}\right)\leq4$, consider the fault-tolerant basis set $B_f = \{{a}_1, {a}_\frac{{♃}+1}{2}, {c}_1, {c}_{\frac{{♃}+1}{2}}\}.$ The interactive depictions of for the vertices of graph are

The inner cycle vertex positions with respect to the fault-tolerant basis set $B_f$ are

The interior vertex positions with respect to the fault-tolerant basis set $B_f$ are

The outer cycle vertex positions with respect to the fault-tolerant basis set $B_f$ are

It is clear to see that the representations of all vertices in Eq (3.4) with respect to the fault-tolerant metric basis set $B_f$ are different, and thus it is proved that $dim_f\left({F}_{♃}\right)\leq4.$

From Theorem 3.1, and Observation 1.2, we directly obtain the converse.

Hence, it is proved that

□

Theorem 3.3. Let ${F}_{♃}$ be a convex polytope graph with ${♃}\geq5$ and ${♃}$ is odd. Then the edge metric dimension of ${F}_{♃}$ is $4.$

Proof. To prove $dim_e\left({F}_{♃}\right)\leq4$, consider the edge basis set $B_e = \{{a}_1, {a}_\frac{{♃}+1}{2}, {c}_1, {c}_{\frac{{♃}+1}{2}}\}.$ The interactive depictions of (3.5) follow:

As the given vector representations in Eq (3.5) of all edges of ${F}_{♃}$ are distinct, we have that $dim_e\left({F}_{♃}\right)\leq4.$

To prove the reverse inequality that $dim_e\left({F}_{♃}\right)\geq4,$ on the contrary it becomes $dim_e\left({F}_{♃}\right) = 3,$ and the following are cases in support of this claim.

Case 1: Let $B^{'}_e\in\{{a}_{☿}\}$ with cardinality three having indices $1\leq {☿}, {j}, {k}\leq {♃};$ similarly, identical expressions are also represented as $r\left({a}_1{a}_{♃}|B^{'}_e\right) = r\left({a}_1{b}_{1}|B^{'}_e\right)$ and $r\left({a}_1{b}_{1}|B^{'}_e\right) = r\left({a}_1{b}_{♃}|B^{'}_e\right)$ with $1\leq {☿}, {j}, {k}\leq \frac{{♃}+1}{2}$ and $\frac{{♃}+1}{2} < {☿}, {j}, {k}\leq {♃},$ respectively.

Case 2: Let $B^{'}_e\in\{{b}_{☿}\}$ with cardinality three having indices $1\leq {☿}, {j}, {k}\leq {♃};$ similarly, identical expressions are also represented as $r\left({a}_1{a}_{2}|B^{'}_e\right) = r\left({c}_1{c}_{2}|B^{'}_e\right)$ or $r\left({a}_1{a}_{♃}|B^{'}_e\right) = r\left({c}_1{c}_{♃}|B^{'}_e\right).$

Case 3: Let $B^{'}_e\in\{{c}_{☿}\}$ with cardinality three having indices $1\leq {☿}, {j}, {k}\leq {♃};$ similarly, identical expressions are also represented as $r\left({a}_1{a}_{2}|B^{'}_e\right) = r\left({a}_2{a}_{3}|B^{'}_e\right)$ or $r\left({a}_1{a}_{♃}|B^{'}_e\right) = r\left({a}_1{b}_{♃}|B^{'}_e\right).$

Case 4: Let $B^{'}_e = \{{a}_{☿}, \ {b}_{☿}, \ {c}_{☿}\}$ with cardinality three having indices $1\leq {☿}\leq {♃};$ similarly, identical expressions are also represented as $r\left({a}_{☿}{a}_{{☿}+1}|B^{'}_e\right) = r\left({a}_{☿}{b}_{☿}|B^{'}_e\right)$ or $r\left({a}_{☿}{b}_{☿}|B^{'}_e\right) = r\left({c}_{☿}{c}_{{☿}+1}|B^{'}_e\right),$ and these same representations remain in the first-circle edges with the last-circle edges if $B^{'}_e = V\left({F}_{♃}\right).$

Every example led to contradictions, indicating that it is not feasible for $B^{'}_e$ to have a cardinality of three. This implies that $dim_e\left({F}_{♃}\right)\neq3$, and thus additionally leads to the conclusion that, for ${♃}\geq5$ and ${♃}$ is odd,

□

Theorem 3.4. Let ${F}_{♃}$ be a convex polytope graph with ${♃}\geq4$ and ${♃}$ is even. Then the edge metric dimension of ${F}_{♃}$ is $5.$

Proof. To prove $dim_e\left({F}_{♃}\right)\leq5$, consider the edge basis set $B_e = \{{a}_1, {a}_2, {a}_\frac{{♃}+2}{2}, {c}_1, {c}_{\frac{♃}{2}}\}.$ The interactive depictions of (3.6) follow:

As the given vector representations in Eq (3.6) of all edges of ${F}_{♃}$ are distinct, we have that $dim_e\left({F}_{♃}\right)\leq5.$ To prove the reverse inequality that $dim_e\left({F}_{♃}\right)\geq5,$ on the contrary it becomes $dim_e\left({F}_{♃}\right) = 4,$ and we have the following discussion in support of this claim.

For even values of ${♃}$, the polytope created by ${♃}$ has a different symmetry than that of the odd values of ${♃}$. This concept arose with a unique gap between different parities on ${♃}$. For example, the distance $d\left({a}_{1}, {a}_\frac{{♃}+1}{2}\right) = \frac{♃}{2}$ either by moving clockwise or anticlockwise on inner circle vertices ${a}_{☿}$ and ${a}_\frac{{♃}+1}{2}$ is the symmetrical vertex of ${a}_{☿}$ vertices which covers the same length from the starting vertex, and this same concept can be applied to the edges of ${a}_{☿}{a}_{{☿}+1}.$ Similarly, if we change the starting point, say ${a}_{{j}+1}$, then the symmetrical vertex becomes ${a}_{\frac{{♃}+2}{2}+{j}}.$ In short, one can find the symmetrical vertex from any of the vertices or edges of the ${a}_{☿}$-circle, which means it has the same distance either clockwise or anticlockwise. But, in the other case when ${♃}$ is odd parity, one can not find such a symmetrical vertex, which does not allow you to have same the representations likewise when ${♃}$ is even.

Similarly, the ${c}_{☿}$-circle is also has a symmetrical vertex for each ${c}_{☿}$ vertex and edge, which results in the same distances and implies the same representations for ${♃} = {even}$, which is not possible for ${♃} = {odd}$ when the cardinality of the edge resolving set is four. The ${b}_{☿}$ vertices and edges also result in having a symmetrical vertex for each ${b}_{☿}$ vertex and edges, and gives the same representation when the cardinality of the edge resolving set is four.

It was determined that for ${♃}\geq4,$ and ${♃}$ is even, as all the cases led to a contradiction and showed that $B^{'}_e$ with cardinality three is impossible. This means that $dim_e\left({F}_{♃}\right)\neq4$ and thus

□

4.   Conclusions

The metric dimension was the first concept of resolvability parameters introduced, and has led researchers to think about graph theory in different ways. Later, fault-tolerant sets and the edge metric dimension were introduced and studied for different structures, and provided some applications of this concept. In this article, we studied the convex polytope graph ${F}_{♃}$ in terms of the above defined parameters, and the results of our research are summarized in Table 1.

Use of AI tools declaration

The author declares he has not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The author declares that he has no conflict of interests.