2022/06/10 by Ali Ghalavand, Sandi Klavžar, Ghalavand, Ali +5
Computer Science · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2206.04983
openalex publication_date 2022/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph and let S(G), M(G), and T(G) be the subdivision, the middle, and the total graph of G, respectively. Let \rm dim(G), \rm edim(G), and \rm mdim(G) be the metric dimension, the edge metric dimension, and the mixed metric dimension of G, respectively. In this paper, for the subdivision graph it is proved that (1)/(2)max\\rm dim(G),\rm edim(G)\≤\rm mdim(S(G))≤\rm mdim(G). A family of graphs Gn is constructed for which \rm mdim(Gn)-\rm mdim(S(Gn))≥ 2 holds and this shows that the inequality \rm mdim(S(G))≤\rm mdim(G) can be strict, while for a cactus graph G, \rm mdim(S(G))=\rm mdim(G). For the middle graph it is proved that \rm dim(M(G))≤\rm mdim(G) holds, and if G is tree with n1(G) leaves, then \rm dim(M(G))=\rm mdim(G)=n1(G). Moreover, for the total graph it is proved that \rm mdim(T(G))=2n1(G) and \rm dim(G)≤\rm dim(T(G))≤ n1(G) hold when G is a tree.