Naslov
Vertex and edge metric dimensions of cacti

Autori
Sedlar, Jelena ; Škrekovski, Riste

Izvornik
Discrete applied mathematics (0166-218X) 320 (2022); 126-139

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
metric dimensions ; cacti

Sažetak
In a graph G, a vertex (resp. an edge) metric generator is a set of vertices S such that any pair of vertices (resp. edges) from G is distinguished by at least one vertex from S. The cardinality of a smallest vertex (resp. edge) metric generator is the vertex (resp. edge) metric dimension of G. In [?] we determined the vertex (resp. edge) metric dimension of unicyclic graphs and that it takes its value from two consecutive integers. Therein, several cycle configurations were introduced and the vertex (resp. edge) metric dimension takes the greater of the two consecutive values only if any of these configurations is present in the graph. In this paper we extend the result to cactus graphs i.e. graphs in which all cycles are pairwise edge disjoint. We do so by defining a unicyclic subgraph of G for every cycle of G and applying the already introduced approach for unicyclic graphs which involves the configurations. The obtained results enable us to prove the cycle rank conjecture for cacti. They also yield a simple upper bound on metric dimensions of cactus graphs and we conclude the paper by conjecturing that the same upper bound holds in general.

Izvorni jezik
Engleski

POVEZANOST RADA