 Metric dimensions vs. cyclomatic number of graphs with minimum degree at least twoJelena Sedlar and Riste Škrekovski Applied Mathematics and Computation, 2022, vol. 427, issue C Abstract: The vertex (resp. edge) metric dimension of a connected graph G, denoted by dim(G) (resp. edim(G)), is defined as the size of a smallest set S⊆V(G) which distinguishes all pairs of vertices (resp. edges) in G. Bounds dim(G)≤L(G)+2c(G) and edim(G)≤L(G)+2c(G), where c(G) is the cyclomatic number in G and L(G) depends on the number of leaves in G, are known to hold for cacti and it is conjectured that they hold for general graphs. In leafless graphs it holds that L(G)=0, so for such graphs the conjectured upper bound becomes 2c(G). In this paper, we show that the bound 2c(G) cannot be attained by leafless cacti, so the upper bound for such cacti decreases to 2c(G)−1, and we characterize all extremal leafless cacti for the decreased bound. We conjecture that the decreased bound holds for all leafless graphs, i.e. graphs with minimum degree at least two. We support this conjecture by showing that it holds for all graphs with minimum degree at least three and that it is sufficient to show that it holds for all 2-connected graphs, and we also verify the conjecture for graphs of small order. Date: 2022 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:427:y:2022:i:c:s0096300322002272 DOI: 10.1016/j.amc.2022.127147 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.