Remarks on the Vertex and the Edge Metric Dimension of 2-Connected Graphs
Open Access
- 10 July 2022
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 10 (14) , 2411
Abstract
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 (respectively ). The upper bounds and where 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 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 in the class of leafless graphs besides already known extremal cacti and extremal -graphs mentioned here.
Keywords
Funding Information
- Slovak Research (VEGA 1/0567/22, VEGA 1/0206/20, APVV-19-0308, APVV–17–0428, P1-0383, J1-1692)
- European Regional Development Fund—the Competitiveness and Cohesion Operational Programme (VEGA 1/0567/22, VEGA 1/0206/20, APVV-19-0308, APVV–17–0428, P1-0383, J1-1692)
- Slovenian Research Agency ARRS Program (VEGA 1/0567/22, VEGA 1/0206/20, APVV-19-0308, APVV–17–0428, P1-0383, J1-1692)
- The Slovenian Research and Innovation Agency (VEGA 1/0567/22, VEGA 1/0206/20, APVV-19-0308, APVV–17–0428, P1-0383, J1-1692)
This publication has 20 references indexed in Scilit:
- On the edge metric dimension of convex polytopes and its related graphsJournal of Combinatorial Optimization, 2019
- Edge Metric Dimension of Some Graph OperationsBulletin of the Malaysian Mathematical Sciences Society, 2019
- On graphs with the maximum edge metric dimensionDiscrete Applied Mathematics, 2019
- Uniquely identifying the edges of a graph: The edge metric dimensionDiscrete Applied Mathematics, 2018
- On the edge dimension of a graphDiscrete Mathematics, 2018
- The metric dimension of Cayley digraphsDiscrete Mathematics, 2006
- On k-dimensional graphs and their basesPeriodica Mathematica Hungarica, 2003
- Resolvability in graphs and the metric dimension of a graphDiscrete Applied Mathematics, 2000
- Landmarks in graphsDiscrete Applied Mathematics, 1996
- Metric bases in digital geometryComputer Vision, Graphics, and Image Processing, 1984