Edge metric dimension of bicyclic graphs

Abstract

Background Slater introduced the ‘metric dimension’(MD) concept in 1975 [4] to provide a framework for uniquely identifying the location of vertices in a connected graph using distances to a specific subset of vertices. In the last decade, this concept has drawn considerable interest from researchers, due to the wide range of applications in computer science, social networks, chemistry, biology, and many others. In 1976, Harary and Melter [5] further investigated the concept and introduced the term ‘resolving set’. The Resolving set is a subset of vertices such that every vertex on the graph can be uniquely identified by its distances to the vertices in this subset, and the MD is the size of the smallest resolving set of that graph. MD has several variants, and ‘edge metric dimension’(EMD) introduced by Kelenc et al. focuses on identifying edges using a minimal resolving set [1]. Notably, this parameter can also be interpreted as the MD of the line graph, where the vertices represent the edges of the original graph and two vertices are connected if they are adjacent in the original graph. EMD is used to design resilient networks and optimize resources in systems. Recently, the EMD of certain families of graphs such as cycles, trees, complete bipartite graphs, trees and circulant graphs has been studied [3]. This study focuses on finding EMD in three types of bicyclic graphs that have not previously been studied. Bicyclic graphs play a vital role in chemical compound analysis, biological networks, and network design etc. Despite significant research on MD, its variant, EMD remained largely unexplored in the context of bicyclic graphs, and the objective here is to fill this research gap.

Methods In this paper, graph is represented by G and it’s line graph as L(G). Vertex set v1, v2, ..., vn and edge set e1, e2, ..., en of G is represented by V (G) and E(G) respectively. For simplicity, edge metric dimension of graph G is represented by (dimE (G)). Three types of bicyclic graphs defined in [2] are used in this research. We denote the number of vertices in two cycles by n and m and the length of the path as r. Type I: Cn,m(n, m ≥ 3): Two disjoint cycles sharing a vertex. Type II: Cn,r,m(n, m ≥ 3, r ≥ 1): Two disjoint cycles connected by a path Type III: (θn,n,n(n ≥ 1)): Three pairs of internally disjoint paths, each of length n, were constructed to connect two vertices.

Starting from the proper labeling of three types of bicyclic graphs(G) and the corresponding line graphs were constructed (Figures 1 to 4). The EMD is determined analytically and using Python simulations by varying the number of vertices in cycles and paths (n, m, r). Resolving sets (W ) were identified, and vertex sets were partitioned based on their distances to W. A case study demonstrated that all vertices have distinct representations with respect to W, establishing |W| as an upper bound for EMD. Using mathematical proofs, the lower bound was also shown to be equal to |W|, concluding that dimE (G) = |W| for the analyzed graphs.

Results and Conclusions The results revealed that all bicyclic graphs have a constant EMD and depend on structural properties, specifically the number of vertices in their cycles and paths. The edge metric dimensions of the type I, II, and III bicyclic graphs are dimE (Cn,m) = 3, dimE (Cn,r,m) = 2, dimE (θn,n,n) = 2, respectively. For a Type I bicyclic graph, the edge metric basis is W = {e1, en, en+m}, for a Type II, W = {e1, en+r+m}, and for a specific case of Type III θ-graphs, W = {e1, en+1}. Having constant EMDs for all bicyclic graphs highlights their efficiency in applications such as resilient network design and molecular modeling. The study contributes to graph theory by addressing a theoretical gap and providing a foundation for exploring metric dimensions in more complex graphs.