Metric dimensions vs. cyclomatic number of graphs with minimum degree at least two

Highlights：

• We prove that the upper bound L(G)+2c(G) for the vertex and the edge metric dimensions of cacti cannot be attained of a cactus graph has no leaves.

• Since in a leafless cacti it holds that L(G)=0, the first next bound is 2c(G)−1, and for this bound we prove that there exist leafless cacti which attain it and we characterize all of them.

• We further conjecture that the decreased upper bound 2c(G)−1 holds for the vertex and the edge metric dimension all graphs without leaves.

• 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.

摘要

•We prove that the upper bound L(G)+2c(G) for the vertex and the edge metric dimensions of cacti cannot be attained of a cactus graph has no leaves.•Since in a leafless cacti it holds that L(G)=0, the first next bound is 2c(G)−1, and for this bound we prove that there exist leafless cacti which attain it and we characterize all of them.•We further conjecture that the decreased upper bound 2c(G)−1 holds for the vertex and the edge metric dimension all graphs without leaves.•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.

论文评审过程：Received 21 August 2021, Revised 29 March 2022, Accepted 1 April 2022, Available online 23 April 2022, Version of Record 23 April 2022.