Computing Metric Dimension of Two Types of Claw-Free Cubic Graphs With Applications

Abstract

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, z1), d(x, z2), ..., d(x, zk)) represents representation of x with respect to R for an ordered subset R = {z1, z2, z3..., zk} 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. © 2024 the Author(s), licensee Combinatorial Press.