Consider the simple connected graph G with vertex set V(G) and edge set E(G). A graph can be resolved by if each vertex’s representation of distances to the other vertices in uniquely identifies it. The minimum cardinality of the set is the metric dimension of . 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 represents representation of with respect to for an ordered subset of vertices and vertex 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) 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.
2. Preliminaries
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
represents representation of with respect to for an ordered subset of vertices
and vertex 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. For example, resolving sets
for the grid graph and complete graph 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 and the complete graph are 2 and 4, respectively.
Figure 1. Resolving Set for Grid (Blue Vertices Belong to the Resolving Set) Figure 2. Resolving Set for (Blue Vertices Belong to the Resolving Set)Figure 3. The Transformation from to Diamond ()
A cubic graph has a three-regular pattern with degree three. A claw
graph is an isomorphic graph to a complete bipartite graph K. A claw-free graph is one in
which no induced subgraph is a claw. Oum investigated simple
claw-free bridgeless cubic graphs in. An induced subgraph of
G that is isomorphic to , is called a diamond and is
symbolized by (See Figure 3). A string of diamonds (SOD) is
the series with
having a vertex adjacent to
(See Figure 4). Furthermore, 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).
Figure 4. A Sting of Diamonds Figure 5. A Ring of Diamonds
3. Results and Discussion
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 and the ring of diamonds simply by The vertices for the string of
diamonds and the ring of
diamonds are labeled according
to Figures 4 and 5,
respectively.
Theorem 1. Let be a String of diamonds and n
is the number of diamonds. Then the metric dimension is given
by:
, if .
provided
.
Proof. The proof is split into two cases:
Case I: For n=.
The vertex and edge sets of graph are
and ,
respectively. Let the resolving set of the graph be . Now the
uniqueness of distances between the vertices in resolving set and all other vertices of graph for will be proved in the following way:
Since all
the above representations are unique, so is the resolving set. Hence . It is known that if and only if
is a path graph. So, if n=.
Case II: For .
The vertex and edge sets of the graph have the following expression: , and , respectively. Consider
the resolving set of the graph is
R= . Now the
uniqueness of the distances between each vertex in graph and the resolving set R will be
demonstrated. The vertices can be articulated as follows in terms of the
resolving set:
For the vertices , For the vertices ,
… Forvertices ,
… Forvertices ,
… For vertices,
… R is the resolving set since each
distance is distinct from the others. So, .
It is additionally required to prove that is the minimum resolving set. In order
to accomplish this, it must be verified that, for . It is
possible to accomplish this by indicating that cannot have a resolving set of order
. Assume for the sake of
argument that has cardinality
and is a resolving set. After
removing
respectively from resolving set, the following representations are same.
…
and
Given that there is contradiction in any distance, they are not all
unique. Hence, a resolving set with elements does not exist. This
completes the proof.
Theorem 2. Let be a ring of diamonds, and n
denotes the number of diamonds. Then the metric dimension is given
by:
,
for n=2.
.
Proof. The two cases that comprise the proof are as
follows:
Case I: For n=.
The vertex and edge sets of graph G have the following
mathematical expression:
and E(G)=, , , , , , . Let be the
resolving set of graph . 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: the minimal set of resolved problems. This can
only be achieved by confirming that. To get this, one must demonstrate that is not capable of having an order 2
resolving set. Upon eliminating we obtain : . Due to the contradiction that two distances
are exactly alike. Consequently, R does not have a resolving
set with cardinality 2. So , for n=2.
Case II: For .
The following is the expression for the vertex and edge sets of graph
: and E. Let R= be the resolving
set of graph . We shall show in
this section that the distances between each vertex in the given graph
and the resolving set are unique. The representation of the
vertices with respect to the resolving set are given as:
As for the vertices , … Forvertices
, … Forvertices
, … For vertices, … R is the resolving set because each
distance is distinct. Hence, .
It is also needed to prove that is the minimum resolving set. To do
this, it must be demonstrated that, for . By showing that is unable to have a resolving set of
order , this can be obtained.
Assume for the moment that has
cardinality and is a resolving
set.
Following their removal from the resolving set, respectively, we
obtain … Considering that the distances are
not all unique there is contradiction. Hence, a resolving set with
cardinality does not exist for
. The proof is now
complete.
4. Applications
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.
5. Conclusion
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.
Acknowledgment
This work was funded in part by the National Natural Science
Foundation of China (Grants Nos. 12071194, 11571155).
Authors’
Declaration
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.
Authors’
Contribution Statement
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.
References:
Slater. P.J. 1975 Leaves of Trees. Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, 14, pp.549-559.
Tillquist, R.C. and Lladser, M.E., 2019. Low-dimensional representation of genomic sequences. Journal of Mathematical Biology, 79(1), pp.1-29.
Hu, J. and Shang, X., 2017. Detection of network motif based on a novel graph canonization algorithm from transcriptional regulation networks. Molecules, 22(12), p.2194.
Shao, Z., Wu, P., Zhu, E. and Chen, L., 2018, October. Metric dimension and robot navigation in specific sensor networks. In 2018 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC) (pp. 369-3694). IEEE.
Khuller, S., Raghavachari, B. and Rosenfeld, A., 1996. Landmarks in graphs. Discrete Applied Mathematics, 70(3), pp.217-229.
Garey, M.R. and Johnson, D.S., 1990. A Guide to the Theory of NP-Completeness. Computers and Intractability, pp.37-79.
Imran, M., Ahmad, A. and Semaničová-feňovčíková, A., 2013. On classes of regular graphs with constant metric dimension. Acta Mathematica Scientia, 33(1), pp.187-206.
Peters-Fransen, Joel and Oellermann, Ortrud R. (2006) “The metric dimension of Cartesian products of graphs”, Utilitas Mathematica , 69.
Imran, M., Baig, A.Q., Bokhary, S.A.U.H. and Javaid, I., 2012. On the metric dimension of circulant graphs. Applied Mathematics Letters, 25(3), pp.320-325.
Buczkowski, P., Chartrand, G., Poisson, C. and Zhang, P., 2003. On k-dimensional graphs and their bases. Periodica Mathematica Hungarica, 46(1), pp.9-15.
Díaz, J., Pottonen, O., Serna, M. and van Leeuwen, E.J., 2017. Complexity of metric dimension on planar graphs. Journal of Computer and System Sciences, 83(1), pp.132-158.
Imran, M., Bokhary, S.A.U.H. and Baig, A.Q., 2010. On families of convex polytopes with constant metric dimension. Computers & Mathematics with Applications, 60(9), pp.2629-2638.
Imran, M., Bashir, F., Baig, A.Q., Bokhary, S.A.U.H., Riasatº, A. and Tomescu, I., 2013. On metric dimension of flower graphs f, g, and convex polytopes”. Utilitas Mathematica, 92, pp.389-409.
Peterin, I. and Yero, I.G., 2020. Edge metric dimension of some graph operations. Bulletin of the Malaysian Mathematical Sciences Society, 43(3), pp.2465-2477.
Liu, J.B., Nadeem, M.F., Siddiqui, H.M.A. and Nazir, W., 2019. Computing metric dimension of certain families of Toeplitz graphs. IEEE Access, 7, pp.126734-126741.
Zhu, E., Taranenko, A., Shao, Z. and Xu, J., 2019. On graphs with the maximum edge metric dimension. Discrete Applied Mathematics, 257, pp.317-324.
Akhter, S. and Farooq, R., 2019. Metric dimension of fullerene graphs. Electron. J. Graph Theory Appl., 7(1), pp.91-103.
Ebrahimi, S., Nikandish, R., Tehranian, A. and Rasouli, H., 2021. On the strong metric dimension of annihilator graphs of commutative rings. Bulletin of the Malaysian Mathematical Sciences Society, 44, pp.2507-2517.
Alshehri, H., Ahmad, A., Alqahtani, Y. and Azeem, M., 2022. Vertex metric-based dimension of generalized perimantanes diamondoid structure. IEEE Access, 10, pp.43320-43326.
Zhang, Y., Hou, L., Hou, B., Wu, W., Du, D.Z. and Gao, S., 2020. On the metric dimension of the folded n-cube. Optimization Letters, 14(1), pp.249-257.
Bashir, H., Zahid, Z., Kashif, A., Zafar, S. and Liu, J.B., 2021. On 2-metric resolvability in rotationally-symmetric graphs. Journal of Intelligent & Fuzzy Systems, 40(6), pp.11887-11895.
Wang, D.G., Wang, M.M. and Zhang, S., 2022. Determining the edge metric dimension of the generalized Petersen graph P (n, 3). Journal of Combinatorial Optimization, 43(2), pp.460-496.
Rezaei, A., Khashyarmanesh, K. and Afkhami, M., 2022. On the metric dimension of Cayley graphs. AKCE International Journal of Graphs and Combinatorics, 19(2), pp.118-124.
Li, S., Liu, J.B. and Munir, M., 2020. On the metric dimension of generalized tensor product of interval with paths and cycles. Journal of Mathematics, 2020, pp.1-6.
Sharma, S.K., Bhat, V.K., Raza, H. and Sharma, S., 2022. On mixed metric dimension of polycyclic aromatic hydrocarbon networks. Chemical Papers, 76(7), pp.4115-4128.
Liu, J.B., Sharma, S.K., Bhat, V.K. and Raza, H., 2023. Multiset and mixed metric dimension for starphene and zigzag-edge coronoid. Polycyclic Aromatic Compounds, 43(1), pp.190-204.
Sharma, S.K., Raza, H. and Bhat, V.K., 2023. Fault-tolerant resolvability of some graphs of convex polytopes. Discrete Mathematics and Applications, 33(3), pp.177-187.
Javaid, M., Raza, M., Kumam, P. and Liu, J.B., 2020. Sharp bounds of local fractional metric dimensions of connected networks. IEEE Access, 8, pp.172329-172342.
Nadeem, A., Kashif, A., Zafar, S., Aljaedi, A. and Akanbi, O., 2022. Fault Tolerant Addressing Scheme for Oxide Interconnection Networks. Symmetry, 14(8), p.1740.
Azhar, K., Zafar, S., Kashif, A., Aljaedi, A. and Albalawi, U., 2022. Fault-tolerant partition resolvability in mesh related networks and applications. IEEE Access, 10, pp.71521-71529.