2022/03/14 by Martin Knor, Knor, Martin, Jelena Sedlar +3 · 1 citation
Computer Science · #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2203.07335
The vertex (resp. edge) metric dimension of a graph G is the size of a\nsmallest vertex set in G which distinguishes all pairs of vertices (resp.\nedges) in G and it is denoted by dim(G) (resp. edim(G)). The upper bounds\ndim(G) <= 2c(G) - 1 and edim(G) <= 2c(G)-1; where c(G) denotes the cyclomatic\nnumber of G, were established to hold for cacti without leaves distinct from\ncycles, and moreover all leafless cacti which attain the bounds were\ncharacterized. It was further conjectured that the same bounds hold for general\nconnected graphs without leaves and this conjecture was supported by showing\nthat the problem reduces to 2-connected graphs. In this paper we focus on Theta\ngraphs, as the most simple 2-connected graphs distinct from cycle, and show\nthat the the upper bound 2c(G) - 1 holds for both metric dimensions of Theta\ngraphs and we characterize all Theta graphs for which the bound is attained. We\nconclude by conjecturing that there are no other extremal graphs for the bound\n2c(G) - 1 in the class of leafless graphs besides already known extremal cacti\nand extremal Theta graphs mentioned here.\n