
arXiv: 2203.07335
The vertex (respectively edge) metric dimension of a graph G is the size of a smallest vertex set in G, which distinguishes all pairs of vertices (respectively edges) in G, and it is denoted by dim(G) (respectively edim(G)). The upper bounds dim(G)≤2c(G)−1 and edim(G)≤2c(G)−1, where c(G) denotes the cyclomatic number of G, were established to hold for cacti without leaves distinct from cycles, and moreover, all leafless cacti that attain the bounds were characterized. It was further conjectured that the same bounds hold for general connected graphs without leaves, and this conjecture was supported by showing that the problem reduces to 2-connected graphs. In this paper, we focus on Θ-graphs, as the most simple 2-connected graphs distinct from the cycle, and show that the the upper bound 2c(G)−1 holds for both metric dimensions of Θ-graphs; we characterize all Θ-graphs for which the bound is attained. We conclude by conjecturing that there are no other extremal graphs for the bound 2c(G)−1 in the class of leafless graphs besides already known extremal cacti and extremal Θ-graphs mentioned here.
vertex metric dimension, metric dimensions ; Theta graph, Theta-graph, vertex metric dimension; edge metric dimension; Theta-graph, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, edge metric dimension, Combinatorics (math.CO), 05C12, Mathematics
vertex metric dimension, metric dimensions ; Theta graph, Theta-graph, vertex metric dimension; edge metric dimension; Theta-graph, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, edge metric dimension, Combinatorics (math.CO), 05C12, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
