Remarks on the Vertex and the Edge Metric Dimension of 2-Connected Graphs

Martin Knor, Jelena Sedlar and Riste Škrekovski
Additional contact information
Martin Knor: Faculty of Civil Engineering, Slovak University of Technology in Bratislava, Radlinského 11, 813 68 Bratislava, Slovakia
Jelena Sedlar: Faculty of Civil Engineering, Architecture and Geodesy, University of Split, 21000 Split, Croatia
Riste Škrekovski: Faculty of Information Studies, 8000 Novo Mesto, Slovenia

Mathematics, 2022, vol. 10, issue 14, 1-16

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 dim ( G ) (respectively edim ( G ) ). The upper bounds dim ( G ) ≤ 2 c ( G ) − 1 and edim ( G ) ≤ 2 c ( 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 2 c ( 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 2 c ( G ) − 1 in the class of leafless graphs besides already known extremal cacti and extremal Θ -graphs mentioned here.

Keywords: vertex metric dimension; edge metric dimension; Theta-graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/14/2411/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/14/2411/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:14:p:2411-:d:859602

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().