Menu
Consider the simple connected graph G with vertex set V(G) and edge set E(G). A graph \(G\) can be resolved by \(R\) if each vertex’s representation of distances to the other vertices in \(R\) uniquely identifies it. The minimum cardinality of the set \(R\) is the metric dimension of \(G\). The length of the shortest path between any two vertices, x, y in V(G), is signified by the distance symbol d(x, y). An ordered k-tuple \(r(x/R)=(d(x,z_1),d(x,\ z_2),…,d(x,z_k))\) represents representation of \(x\) with respect to \(R\) for an ordered subset \(R={\{z}_1,z_2,z_3…,z_k\}\) of vertices and vertex \(x\) in a connected graph. Metric dimension is used in a wide range of contexts where connection, distance, and connectedness are essential factors. It facilitates understanding the structure and dynamics of complex networks and problems relating to robotics network design, navigation, optimization, and facility location. Robots can optimize their localization and navigation methods using a small number of reference sites due to the pertinent idea of metric dimension. As a result, many robotic applications, such as collaborative robotics, autonomous navigation, and environment mapping, are more accurate, efficient, and resilient. A claw-free cubic graph (CCG) is one in which no induced subgraph is a claw. CCG proves helpful in various fields, including optimization, network design, and algorithm development. They offer intriguing structural and algorithmic properties. Developing algorithms and results for claw-free graphs frequently has applications in solving of challenging real-world situations. The metric dimension of a couple of claw-free cubic graphs (CCG), a string of diamonds (SOD), and a ring of diamonds (ROD) will be determined in this work.
The metric dimension of a graph is the smallest number of nodes required to identify all other nodes uniquely based on shortest path distances. In 1975, Slater proposed the concept of metric dimension [1]. Metric dimension in graphs has applications in a wide range of areas, including location detection [1], embedding DNA sequences in real space [2], detecting network motifs [3], robotics [4], navigation [5] and more. It offers practical knowledge of the structure and properties of graphs, which can be used to effectively solve real-world issues and achieve decisions in a variety of circumstances.
On the other hand, several authors have proposed alternate forms of metric generators to emphasize different perspectives on metric generators. Resolving dominating sets [6], independent resolving sets [7, 8, 9], local metric sets [10, 11], k-metric generators [12], resolving partitions [13], and other concepts have been presented and investigated. There are several other articles in the literature that are pretty intriguing about the metric dimension of graphs. However, due to the large number of results on this topic, just those publications are cited that are relevant in our opinion.
Peterin and Yero [14] created novel graphs by employing graph operations such as graph join, lexicographic product, and corona product. They then calculate the edge metric dimensions for these newly formed graphs. Liu et al. [15] calculated the metric dimension of specific classes of Toeplitz graphs and demonstrated that the metric dimension remains constant for these classes of graphs. Zhu et al. [16] determined the structure of graphs that yield the highest edge metric dimension, and derived numerous necessary and sufficient requirements for a graph. Based on these findings, they devised an algorithm with a temporal complexity of O(n\({}^{3}\)) that determines whether a graph of size n reaches an upper limit. In addition, they discussed and resolved a fascinating category of extremal graphs, where the graphs acquired by adding one edge are not the same as the graph that achieves the upper bound for edge metric dimension. Akhter and Farooq [17] examined the (3, 6)-fullerene and (4, 6)-fullerene graphs and calculated the metric dimension for these graphs. In addition, they provided speculation regarding the metric dimension of (3, 6)-fullerene and (4, 6)-fullerene graphs. Ebrahimi et al. [18] conducted research on the strong metric dimension of annihilator graphs linked to commutative rings. They provided several equations for the strong metric dimension of these graphs. Alshehri et al. [19] examined the metric dimension and its generalizations for the generalized perimantanes diamondoid structure. They demonstrated that each parameter is contingent upon the number of copies of the original or base perimantanes diamondoid structure, and varies with the parameter n. Zhang et al. [20] examined the issue of determining the metric dimension of a folded n-cube. The researchers determined the upper limits of the metric dimension of the folded n-cube by creating minimal resolving sets for the n-cube. Bashir et al. [21]calculated the 2-metric dimension of rotationally symmetric plane graphs and determined that it is unaffected by the number of vertices. Wang et al. [22] demonstrated that for n more than 10, the Petersen graph P(n, 3) has an edge dimension of 4. They achieved this by providing a semi-combinatorial proof of the nonexistence of an edge resolving set of order 3, and by explicitly creating an edge resolving set of order 4. Rezaei et al. [23] examined the metric dimension, local metric dimension, and edge metric dimension of certain (generalized) Cayley graphs. Li et al. [24] created two graphs by utilizing the tensor of a path graph with a path and the tensor product of a path with a cycle. Additionally, they established the foundation for these graphs and the presentation of resolving vectors in a comprehensive closed form, specifically in relation to the basis. Sharma et al. [25] examined the resolvability parameter, namely the mixed metric dimension, for the intricate molecular structure of the Polycyclic aromatic hydrocarbons network. Additionally, they demonstrated that the mixed metric dimension of the Polycyclic aromatic hydrocarbons network is not limited and does not remain constant. Liu et al. [26] examined the chemical structures of starphene and six-sided hollow coronoid and calculated their multiset dimension and mixed metric dimension. Sharma et al. [27] calculated the metric dimension and the fault-tolerant metric dimension for three sets of convex polytope graphs. Their primary findings confirm that the three families, previously described, possess consistent fault-tolerant resolvability structures. Javaid et al. [28] developed a computer method to calculate the local fractional metric dimension of connected networks using precise lower and upper bounds. The study provides a comprehensive analysis of connected networks that achieve the minimum local fractional metric dimension. Additionally, it examines specific types of networks (complete networks, generalized windmills, and h-level windmills) that achieve the maximum local fractional metric dimension. The local fractional metric dimension of wheel-related networks (including anti-web gear, m-level wheel, prism, helm, and flower) is computed based on the major found criteria. The boundedness or unboundedness of these networks is further demonstrated using 2D and 3D graphical representations. Nadeem et al. [29] calculated the partition and fault-tolerant partition resolvability of oxide interconnection networks, encompassing single oxide chain networks, rhombus oxide networks, and standard triangulene oxide networks. In addition, this paper includes an implementation of fault resistant partitioning for region-based routing in networks. Azhar et al. [30] examined the partition and fault-tolerant partition resolvability of specific triangular mesh networks, including triangular ladder, triangular mesh, reflection triangular mesh, tower triangular mesh, and reflection tower triangular mesh networks. This demonstrates that the fault-tolerant partition dimension of these networks is 4, while the partition dimension is 3. Continuing the abovementioned investigation, we shall calculate the metric dimensions of two distinct types of claw-free cubic graphs graphs-a string of diamonds (SOD) and a ring of diamonds (ROD) in this paper.
Consider the simple connected graph G with vertex set V(G) and edge set E(G). The length of the shortest path between any two vertices, x, y in V(G), is signified by the distance symbol d(x, y). An ordered k-tuple \(r(x/R)=(d(x,z_1),d(x,\ z_2),…,d(x,z_k))\) represents representation of \(x\) with respect to \(R\) for an ordered subset \(R={\{z}_1,z_2,z_3…,z_k\}\) of vertices and vertex \(x\) in a connected graph. If each vertex of the graph can be uniquely identified by its distances from the vertices of the resolving set, then the set R is called a resolving set and the minimal cardinality of the resolving set is called metric dimension of the G and is abbreviated as \(\beta (G)\)\({}^{31}\). For example, resolving sets for the grid graph \(G_{4,3}\)\({}_{\ }\)and complete graph \(K_5\)\({}_{\ }\)are shown in Figure 1 and 2 respectively. In Figure 1 and Figure 2, the vertices filled with the color blue represent the vertices of the resolving set, so the metric dimension of the grid graph \(G_{4,3}\) and the complete graph \(K_5\) are 2 and 4, respectively.
A cubic graph has a three-regular pattern with degree three. A claw graph is an isomorphic graph to a complete bipartite graph K\({}_{1,3}\). A claw-free graph is one in which no induced subgraph is a claw\({}^{32}\). Oum investigated simple claw-free bridgeless cubic graphs in\({}^{33}\). An induced subgraph of G that is isomorphic to \(K_4-e\), is called a diamond and is symbolized by \(L\) (See Figure 3). A string of diamonds (SOD) is the series \(L_1,…,\ L_n,\) with \(L_i\ \)having a vertex adjacent to \(L_{i+1}\) (See Figure 4). Furthermore, \(G\) is commonly referred to as the ring of diamonds (ROD) if it is a connected claw-free and cubic graph with each vertex lies in the diamond (See Figure 5).
In this section, the metric dimension of two different classes of Claw-free cubic (CCG) graphs, i.e., SOD and ROD, will be determined. Here, we denote the string of diamonds \(L_n\ \)and the ring of diamonds \(R_n\) simply by \(G.\) The vertices for the string of diamonds \(L_n\ \)and the ring of diamonds \(R_n\) are labeled according to Figures 4 and 5, respectively.
Theorem 1. Let \(G\) be a String of diamonds and n is the number of diamonds. Then the metric dimension is given by:
\(\beta (G)=2\), if \(n=1\).
\(\beta (G)=n,\ \)provided \(n\ge 2\).
Proof. The proof is split into two cases:
The vertex and edge sets of graph \(G\) are \(V\left(G\right)=\left\{a_1,b_1,c_1,d_1{,x_1,x}_2\right\}\) and \(E\left(G\right)=\left\{x_1a_1,a_1b_1,b_1d_1,{a_1c}_1,{c_1d}_1{,d}_1x_2\right\}\), respectively. Let the resolving set of the graph \(G\) be \(\left\{x_1,b_1\right\}\). Now the uniqueness of distances between the vertices in resolving set \(R\ \)and all other vertices of graph \(G\) for \(n=1\) will be proved in the following way: \[{r(x}_1|R)=\left\{0,\ 2\right\}, {r(a}_1|R)=\left\{1,\ 1\right\},\mathrm{\ }{r(b}_1|R)=\left\{2,\ 0\right\},\mathrm{\ }{r(c}_1\left|R\right)=\ \left\{2,\ 1\right\},\] \[{r(d}_1\left|R\right)=\left\{3,\ 1\right\},{r(x}_2\left|R\right)=\left\{4,\ 2\right\}.\] Since all the above representations are unique, so \(R\) is the resolving set. Hence \(\beta (G)\le 2\). It is known that \(\beta \left(G\right)=1\ \)if and only if \(G\) is a path graph. So, \(\beta (G)=2\) if n=\(1\).
The vertex and edge sets of the graph \(G\) have the following expression: \(V\left(G\right)=\left\{a_j,b_j,c_j,d_j\ ;\ 1\le j\le n\right\}\cup \{x_1,x_2\)\(\mathrm{\}}\), and \(E\left(G\right)=\left\{a_jb_j,a_jc_j,b_jd_j{,b}_jc_j{,c}_jd_j;1\le j\le n\ \right\}\cup \{x_1a_1,x_2d_n\}\), respectively. Consider the resolving set of the graph \(G\) is R= \({\{b}_j;\ 1\le j\le n\}\). Now the uniqueness of the distances between each vertex in graph \(G\) and the resolving set R will be demonstrated. The vertices can be articulated as follows in terms of the resolving set:
For the vertices \(\left(x_{1\ }{,x_{2\ }\ ;\ 1\le j\le n}_{\ }\right)\), \[{r(x}_1\left|R\right)=\left\{(3j-1),\ 1\le j\le n\right\},\] \[{r(x}_2|R)=\left\{\left(3n-1\right),\ \left(3n-4\right),\ \left(3n-7\right),\ \dots ,\ 8,\ 5,\ 2\right\}.\] For the vertices \(\left(a_j{,\ 1\le j\le n}_{\ }\right)\), \[{r(a}_1\left|R\right)=\left\{\left(3j-2\right),\ 1\le j\le n\right\},\] \[{r(a}_2|R)=\left\{\left(2,\ 3j-5\right),\ 2\le j\le n\right\},\] \[{r(a}_3|R)=\left\{\left(5,\ 2,\ 3j-8\right),\ 3\le j\le n\right\},\] \[{r(a}_4|R)=\left\{\left(8,\ 5,\ 2,\ 3j-11\right),\ 4\le j\le n\right\},\] \[{r(a}_5|R)=\left\{\left(11,\ 8,\ 5,\ 2,\ 3j-14\right),\ 5\le j\le n\right\},\] … \[{r(a}_n\left|R\right)=\left\{\ \left(3n-4,\ 3n-7,…,\ 11,\ 8,\ 5,\ 2,\ 1\right)\right\}.\] For\(\ \)vertices \(\left(b_i{,\ 1\le j\le n}_{\ }\right)\), \[{r(b}_1|R)=\left\{\left(3j-3\right),\ 1\le j\le n\right\},\] \[{r(b}_2\left|R\right)=\left\{\left(3,\ 3j-6\ \right),\ 2\le j\le n\right\},\] \[{r(b}_3|R)=\left\{\left(6,\ 3,\ 3j-9\right),\ 3\le j\le n\right\},\] \[{r(b}_4|R)=\left\{\left(9,\ 6,\ 3,\ 3j-12\right),\ 4\le j\le n\right\},\] \[{r(b}_5|R)=\left\{\left(12,\ 9,\ 6,\ 3,\ 3j-15\right),\ 5\le j\le n\right\},\] … \[{r(b}_n\left|R\right)=\left\{\left(3n,\ 3n-3,\ 3n-6,\ 3n-9,…,\ 6,\ 3,\ 0\right)\right\}.\] For\(\ \)vertices \(\left(c_j{,\ 1\le j\le n}_{\ }\right)\), \[{r(c}_1|R)=\left\{\left(1,\ 3j-3\right),\ 2\le j\le n\right\},\] \[{r(c}_2|R)=\left\{\left(3,1,\ 3j-6\right),\ 3\le j\le n\right\},\] \[{r(c}_3|R)=\left\{\left(6,\ 3,1,\ 3j-9\right),\ 4\le j\le n\right\},\] \[{r(c}_4|R)=\left\{\left(9,\ 6,\ 3,\ 1,\ 3j-12\right),\ 5\le j\le n\right\},\] \[{r(c}_5|R)=\left\{\left(12,\ 9,\ 6,\ 3,1,\ 3j-15\right),\ 6\le j\le n\right\},\] … \[{r(c}_n\left|R\right)=\left\{\left(3n-3,\ 3n-6,\ 3n-9,..,\ 9,\ 6,\ 3,\ 1\ \right)\right\}.\] For vertices\(\ \left(d_i{,\ 1\le j\le n}_{\ }\right)\), \[{r(d}_1|R)=\left\{\left(1,\ 3j-4\right),\ 2\le j\le n\right\},\] \[{r(d}_2|R)=\left\{\left(2,\ 1,\ 3j-7\right),\ 3\le j\le n\right\},\] \[{r(d}_3|R)=\left\{\left(5,\ 2,\ 1,\ 3j-10\right),\ 4\le j\le n\right\},\] \[{r(d}_4|R)=\left\{\left(8,\ 5,\ 2,\ 1,\ 3j-13\right),\ 5\le j\le n\right\},\] \[{r(d}_5|R)=\left\{\left(11,\ 8,\ 5,\ 2,\ 1,\ 3j-17\right),\ 6\le j\le n\right\},\] … \[{r(d}_n\left|R\right)=\{(3n-2,\ 3n-5,\ 3n-8,..,\ 7,\ 4,\ 1)\}.\] R is the resolving set since each distance is distinct from the others. So, \(\beta (G)\le n\).
It is additionally required to prove that \(R\) is the minimum resolving set. In order to accomplish this, it must be verified that, for \(n\ge 2,\ \beta (G)\neq n-1\). It is possible to accomplish this by indicating that \(G\) cannot have a resolving set of order \(n-1\). Assume for the sake of argument that \(R\) has cardinality \(n-1\ \)and is a resolving set. After removing \((b_1,\ b_2,…,\ b_n)\) respectively from resolving set, the following representations are same. \[b_1:\mathrm{\ }d(b_1|b_j)\mathrm{\ }=\mathrm{\ }d\left(c_1{|b}_j\right),\] \[b_2\mathrm{:}\ d(b_2|b_j)\mathrm{\ }=\mathrm{\ }d\left(c_2{|b}_j\right),\] \[b_3\mathrm{:}\ d(b_3|b_j)\mathrm{\ }=\mathrm{\ }d\left(c_3{|b}_j\right),\] …
and \(b_n\mathrm{:}\ d(b_n|b_j)\mathrm{\ }=\mathrm{\ }d\left(c_n{|b}_j\right),\)
Given that there is contradiction in any distance, they are not all unique. Hence, a resolving set with \(n-1\) elements does not exist. This completes the proof.
◻
Theorem 2. Let \(G\) be a ring of diamonds, and n denotes the number of diamonds. Then the metric dimension is given by:
\(\beta \left(G\right)=3\), for n=2.
\(\beta (G)=n,\ where\ n\ge 3\).
Proof. The two cases that comprise the proof are as follows:
The vertex and edge sets of graph G have the following mathematical expression: \(V\left(G\right)=\left\{a_1,b_1,c_1,d_1{{,a}_2{{,b}_2,c}_2,d}_2\right\}\) and E(G)=\(\{\)\(a_1b_1\), \(a_1c_1\), \(b_1c_1\), \(b_1d_{1,\ }d_1a_2,\ a_2b_2\), \(a_2c_2\), \(b_2c_2\), \(b_2d_{2\ },\mathrm{\ }d_2a_1\)\(\mathrm{\}}\). Let \(R=\left\{b_1{,a}_2{,b}_2\right\}\) be the resolving set of graph \(G\). Now, we will showcase the uniqueness of the distances between every vertex in the given graph and the resolving set. Keeping in view the representation of the vertices in the resolving set, we have: \[{r(a}_1|R)=\left\{1,\ 3,\ 2\right\},\mathrm{\ }{r(a}_2|R)=\left\{2,0,1\right\},{r(b}_1\left|R\right)=\left\{\ 0,2,3\right\},\mathrm{\ }{r(b}_2\left|R\right)=\ \left\{3,1,0\right\},\mathrm{\ }{r(c}_1\left|R\right)=\ \left\{1,2,3\right\},\] \[{r(c}_2\left|R\right)=\ \left\{3,1,1\right\},\mathrm{\ }{r(d}_1|R)=\left\{\ 1,1,2\right\},\mathrm{\ }{r(d}_2\left|R\right)=\left\{2,2,1\right\}\] \[\mathrm{As\ each\ distance\ is\ unique,\ }R\mathrm{\ is\ the\ resolving\ set}.\ \mathrm{So},\ \beta \left(G\right)=3.\mathrm{\ It\ is\ also\ necessary\ to\ show\ that\ }R\mathrm{\ is}\] the minimal set of resolved problems. This can only be achieved by confirming that\(\beta (G)\neq 2\). To get this, one must demonstrate that \(R\) is not capable of having an order 2 resolving set. \[\mathrm{\ Let}\ R\ \mathrm{be\ a\ resolving\ set\ of\ cardinality\ two\ for\ the\ purposes\ of\ this\ discussion.}\] Upon eliminating \(b_1,\ a_2,\ and\ b_2,\) we obtain \(b_1\): \(d(b_1|R)\mathrm{\ }=\mathrm{\ }d\left(c_1|R\right)=\left\{\ 2,3\right\}\). \[a_2\mathrm{:}\ d\left(a_1\mathrel{\left|\vphantom{a_1 R}\right.}R\right)\mathrm{\ }=\mathrm{\ }d\left(d_1\mathrel{\left|\vphantom{d_1 R}\right.}R\right)\ =\left\{\ 1,2\right\}.\] \[b_2\mathrm{:}\ d\left(b_2\mathrel{\left|\vphantom{b_2 R}\right.}R\right)\mathrm{\ }=\mathrm{\ }d\left(b_2\mathrel{\left|\vphantom{b_2 R}\right.}R\right) = \left\{3,1\right\}.\] Due to the contradiction that two distances are exactly alike. Consequently, R does not have a resolving set with cardinality 2. So \(\beta \left(G\right)=3\), for n=2.
The following is the expression for the vertex and edge sets of graph \(G\): \(V\left(R_n\right)=\left\{a_j,b_j,c_j,d_j\ ;\ 1\le j\le n\right\}\ \)and E\(\left(R_n\right)=\left\{a_jb_j,a_jc_j,b_jd_j{,b}_jc_j{,c}_jd_j,\ ;1\le j\le n\ \right\}\bigcup \{d_ja_{j+1},1\le j\le n-1\ \}\bigcup \{a_1d_n\}\). Let R= \({\{b}_j;\ 1\le j\le n\}\) be the resolving set of graph \(G\). We shall show in this section that the distances between each vertex in the given graph \(G\) and the resolving set \(R\) are unique. The representation of the vertices with respect to the resolving set are given as:
As for the vertices \(\left(a_j{,\ 1\le j\le n}_{\ }\right)\), \[{r(a}_1|R)=\left\{ \begin{array}{c} \left(3j-2\right),\ 1\le j\le \left\lceil \frac{n}{2}\right\rceil \\ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lceil \frac{n}{2}\right\rceil +1\right)-7,…,\ 11,\ 8,\ 5,\ 2\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left((\frac{n}{2})+1\right)-4,…\ 11,\ 8,\ 5,\ 2;if\ n\ is\ even \end{array} \right)\ \end{array} \right\}\] \[{r(a}_2|R)=\left\{ \begin{array}{c} \left(2,\ 3j-5\right),\ 2\le j\le \left\lceil \frac{n}{2}\right\rceil +1 \\ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lceil \frac{n}{2}\right\rceil +1\right)-7,…,\ 11,\ 8,\ 5\ ;\ if\ n\ is\ odd \\ \mathrm{\ }3\left((\frac{n}{2})+1\right)-4,…\ 11,\ 8,\ 5;\ if\ n\ is\ even \end{array} \right)\ \end{array} \right\},\] \[{r(a}_3\left|R\right)=\mathrm{\ }\left\{ \begin{array}{c} \left(5,2,\ 3j-8\right),\ 3\le j\le \left\lceil \frac{n}{2}\right\rceil +2 \\ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lceil \frac{n}{2}\right\rceil +2\right)-10,…,\ 11,\ 8\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]+2\right)-4,…\ 11,\ 8\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \right\}\] … \[{r(a}_n|R)=\mathrm{\ }\left\{ \begin{array}{c} \left(3j+1\right),\ 1\le j\le \left(\frac{n}{2}\right)-1,if\ n\ is\ even. \\ \begin{array}{c} \mathrm{\ }3\left(\left(\frac{n}{2}\right)-1\right)-1,…,\ 8,\ 5,\ 2,\ 1\ ;if\ n\ is\ even \\ \end{array} \ \end{array} \right\}\] \[{r(a}_n|R)=\mathrm{\ }\left\{ \begin{array}{c} \left(3j+1\right),\ 1\le j\le \left\lfloor \frac{n}{2}\right\rfloor ,if\ n\ is\ odd. \\ \begin{array}{c} \mathrm{\ }3\left(\left\lfloor \frac{n}{2}\right\rfloor -1\right)-1,…,\ 8,\ 5,\ 2,\ 1\ ;if\ n\ is\ odd \\ \end{array} \ \end{array} \right\}\] For\(\ \)vertices \(\left(b_j{,\ 1\le j\le n}_{\ }\right)\), \[{r(b}_1|R)=\left\{ \begin{array}{c} \left(3j-3\right),\ 1\le j\le \left\lceil \frac{n}{2}\right\rceil \\ \left( \begin{array}{c} 3\left(\left\lceil \frac{n}{2}\right\rceil +1\right)-6,…,\ 15,\ 12,\ 9,\ 6,\ 3\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]+1\right)-3,…,\ 15,\ 12,\ 9,\ 6,\ 3\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \right\},\] \[{r(b}_2|R)=\left\{ \begin{array}{c} \left(3,3j-3\right),\ 2\le j\le \left\lceil \frac{n}{2}\right\rceil +1 \\ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lceil \frac{n}{2}\right\rceil +1\right)-6,…,\ 15,\ 12,\ 9,\ 6\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]+1\right)-3,…\ 15,\ 12,\ 9,\ 6\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \right\},\] \[{r(b}_3\left|R\right)=\left\{ \begin{array}{c} \left(6,\ 3,\ 3j-9\right),\ 3\le j\le \left\lceil \frac{n}{2}\right\rceil +2 \\ \ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lceil \frac{n}{2}\right\rceil +2\right)-9,…15,\ 12,\ 9\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]+2\right)-6,…,\ 15,\ 12,\ 9\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \right\},\] … \[{r(b}_n|R)=\mathrm{\ }\left\{\ \begin{array}{c} 3j,\ 1\le j\le \left\lfloor \frac{n}{2}\right\rfloor \\ \ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lfloor \frac{n}{2}\right\rfloor +2\right)-9,…,\ 6,\ 3,\ 0\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left\lfloor \frac{n}{2}\right\rfloor +2\right)-6,…,\ 6,\ 3,\ 0\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \ \right\}\] For\(\ \)vertices \(\left(c_j{,\ 1\le j\le n}_{\ }\right)\), \[{r(c}_1|R)=\left\{ \begin{array}{c} \left(1,3j-3\right),\ 2\le j\le \left\lceil \frac{n}{2}\right\rceil \\ \ \left( \begin{array}{c} 3\left(\left\lceil \frac{n}{2}\right\rceil +1\right)-6,…,15,\ 12,\ 9,\ 6,\ 3\ ;\ if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]+1\right)-3,…,\ 15,\ 12,\ 9,\ 6,\ 3\ ;\ if\ n\ is\ even \end{array} \right)\ \end{array} \right\},\] \[{r(c}_2|R)=\left\{ \begin{array}{c} \left(3,1,3j-6\right),\ 3\le j\le \left\lceil \frac{n}{2}\right\rceil +1 \\ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lceil \frac{n}{2}\right\rceil +1\right)-6,…,\ 15,\ 12,\ 9,\ 6\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]+1\right)-3,…\ 15,\ 12,\ 9,\ 6\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \right\},\] \[{r(c}_3|R)=\left\{ \begin{array}{c} \left(6,3,1,3j-9\right),\ 3\le j\le \left\lceil \frac{n}{2}\right\rceil +2 \\ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lceil \frac{n}{2}\right\rceil +2\right)-9,…,\ 15,\ 12,\ 9\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]+2\right)-6,…,\ 15,\ 12,\ 9\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \right\},\] … \[{r(c}_n|R)=\mathrm{\ }\left\{\ \begin{array}{c} \left(3j\right),\ 1\le j\le \left\lfloor \frac{n}{2}\right\rfloor \\ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lfloor \frac{n}{2}\right\rfloor \right),…,\ 6,\ 3,\ 1\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]\right)-3,…,\ 6,\ 3,\ 1\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \ \right\}\] For vertices\(\left(d_j{,\ 1\le i\le n}_{\ }\right)\), \[{r(d}_1|R)=\left\{ \begin{array}{c} \left(1,3j-4\right),\ 2\le j\le \left\lfloor \frac{n}{2}\right\rfloor +1 \\ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lfloor \frac{n}{2}\right\rfloor +1\right)-2,…,\ 13,10,\ 7,\ 4\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]+1\right)-5,…,\ 13,\ 10,\ 7,\ 4\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \right\},\] \[{r(d}_2|R)=\left\{ \begin{array}{c} \left(4,1,3j-7\right),\ 3\le j\le \left\lfloor \frac{n}{2}\right\rfloor +2 \\ \left( \begin{array}{c} 3\left(\left\lfloor \frac{n}{2}\right\rfloor +2\right)-5,…,\ 13,\ 10,\ 7\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]+2\right)-8,…\ 13,10,\ 7\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \right\},\] \[{r(d}_3|R)=\left\{ \begin{array}{c} \left(7,\ 4,\ 1,\ 3j-7\right),\ 4\le j\le \left\lfloor \frac{n}{2}\right\rfloor +3 \\ \left( \begin{array}{c} 3\left(\left\lfloor \frac{n}{2}\right\rfloor +3\right)-8,…,\ 16,\ 13,\ 10\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]+3\right)-11,…\ 16,\ 13,\ 10\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \right\},\] … \[{r(d}_n|R)=\ \left\{\ \begin{array}{c} \left(3j-1\right),\ 1\le j\le \left\lfloor \frac{n}{2}\right\rfloor \\ \left( \begin{array}{c} \mathrm{\ }3\left(\left\lfloor \frac{n}{2}\right\rfloor \right)+1,…,\ 6,\ 3,\ 1\ ;if\ n\ is\ odd \\ \mathrm{\ }3\left(\left[\frac{n}{2}\right]\right)-2,…,\ 7,\ 4,\ 1\ ;if\ n\ is\ even \end{array} \right)\ \end{array} \ \right\}\] R is the resolving set because each distance is distinct. Hence, \(\beta (G)\ge n\).
It is also needed to prove that \(R\) is the minimum resolving set. To do this, it must be demonstrated that, for \(n\ge 3,\ \beta (G)\neq n-1\). By showing that \(R_n\) is unable to have a resolving set of order \(n-1\), this can be obtained. Assume for the moment that \(R\) has cardinality \(n-1\) and is a resolving set.
Following their removal from the resolving set, \(b_1,\ b_2,…,\ b_n,\) respectively, we obtain \[b_1: d(b_1|b_j)\mathrm{\ }=\mathrm{\ }d\left(c_1{|b}_j\right),\] \[b_2\mathrm{:}\ d(b_2|b_j)\mathrm{\ }=\mathrm{\ }d\left(c_2{|b}_j\right),\] \[b_3\mathrm{:}\ d(b_3|b_j)\mathrm{\ }=\mathrm{\ }d\left(c_3{|b}_j\right),\] … \[b_n,\ d(n|b_j)\mathrm{\ }=\mathrm{\ }d\left(c_n{|b}_j\right),\] Considering that the distances are not all unique there is contradiction. Hence, a resolving set with cardinality \(n-1\) does not exist for \(R\). The proof is now complete.
◻
The concept of metric dimension, which is basic to graph theory, can be put to use in a variety of applications, including but not limited to network architecture, facility location, navigational systems, and sensor positioning. An application of metric dimension linked to the sensor’s location is considered here. The metric dimension is used to identify the minimal number of sensors required to ensure comprehensive coverage and connectivity in a network. MD helps eliminate redundancy, improve the efficiency of data transmission and network connectivity, strengthen the fault tolerance of the network, and lower power consumption by limiting the number of active sensors. Additionally, the metric dimension enables the customization of sensor placement to maintain efficient coverage and connectivity. Let’s suppose a sensor network that monitors a hazardous material pipeline network, where the metric dimension is important to sensor placement.
A company operates an extensive pipeline network that delivers dangerous chemicals through remote and inaccessible terrain. In order to ensure the prevention of leaks, it is imperative to detect potential hazards and promptly address any accidents that may occur, hence maintaining the security and integrity of these pipelines. The organization holds the belief that implementing a sensor network is the optimal approach for monitoring pipelines and their immediate environment.
This paragraph examines the limitations or prerequisites. The coverage obligation entails continuous monitoring of the whole pipeline network and its surrounding area to identify any leaks or potential dangers promptly. However, the implementation of sensors is constrained by the limited availability of resources, leading to a constrained budget and a limited number of sensors that may be used. In order to achieve real-time monitoring, the sensors must establish immediate communication with each other and a central control system to promptly convey information regarding abnormalities or emergencies. Moreover, the sensor network must have the capacity to endure sensor failures or damage caused by environmental factors.
We shall employ the metric dimension approach to optimize the efficiency of sensor placement in the pipeline network. The objective is to select the minimum number of sensor locations throughout the entire network that, when activated, can precisely determine the precise location of a security breach or potential threat.
The metric dimension is helpful in this problem in the following way: in strategic sensor placement; determining the resolving set of the network enables the organization to locate sensors at particular points; these resolving set nodes serve as landmarks, guaranteeing that a minimal number of sensors are required to uniquely identify any point along the pipeline; and identifying critical locations (nodes) in the network corresponds to the resolving set of nodes, in efficient data collection; sensors positioned at the nodes of the resolving set enable the efficient collection and transfer of data. They serve as relay stations, reducing the number of required hops for information to reach the centralized control system, in fault tolerance; If a sensor becomes inoperative due to damage or failure, the network can still function and sufficient coverage can be ensured by other sensors strategically placed at resolving set nodes, in cost optimization, The company optimizes resource use by deploying a reduced number of sensors through strategic sensor placement based on resolving predetermined criteria. This guarantees comprehensive coverage of the whole pipeline network.
The organization can develop an effective and dependable sensor network by using resolving set or metric dimension in sensor placement. This network will monitor pipeline infrastructure and optimize costs and resources.
The concept of metric dimension is readily comprehensible. Due to its strong correlation with GPS and trilateration, the applications involving the identification of graph nodes are easily noticeable. Conversely, determining the exact metric dimension of generic graphs is a highly challenging problem. In this paper, the metric dimension of two kinds of CCG graphs-the ring of diamonds (ROD) and the string of diamonds (SOD) is calculated. These results can be utilized to address challenges of robotics network design, optimization and facility location, as well as for understanding the structure and dynamics of complicated networks.
This work was funded in part by the National Natural Science Foundation of China (Grants Nos. 12071194, 11571155).
Authors declare that they do not have nay conflict of interests.
We hereby confirm that all the Figures and Tables in the manuscript are ours. Furthermore, any Figures and images, that are not ours, have been included with the necessary permission for re-publication, which is attached to the manuscript.
This study was conducted collaboratively by all authors. M.S.S., S.X., and M.C. collaborated on the development and execution of the research. M.S.S., M.R.F., M.A., and S.P. conducted an analysis of the results and composed the manuscript. All authors read and approved the final manuscript.