Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Metric dimension on sparse graphs and its applications to zero forcing sets

Abstract : The metric dimension dim(G) of a graph G is the minimum cardinality of a subset S of vertices of G such that each vertex of G is uniquely determined by its distances to S. It is wellknown that the metric dimension of a graph can be drastically increased by the modification of a single edge. Our main result consists in proving that the increase of the metric dimension of an edge addition can be amortized in the sense that if the graph consists of a spanning tree T plus c edges, then the metric dimension of G is at most the metric dimension of T plus 6c. We then use this result to prove a weakening of a conjecture of Eroh et al. The zero forcing number Z(G) of G is the minimum cardinality of a subset S of black vertices (whereas the other vertices are colored white) of G such that all the vertices will turned black after applying finitely many times the following rule: a white vertex is turned black if it is the only white neighbor of a black vertex. Eroh et al. conjectured that, for any graph G, dim(G) ≤ Z(G) + c(G), where c(G) is the number of edges that have to be removed from G to get a forest. They proved the conjecture is true for trees and unicyclic graphs. We prove a weaker version of the conjecture: dim(G) ≤ Z(G) + 6c(G) holds for any graph. We also prove that the conjecture is true for graphs with edge disjoint cycles, widely generalizing the unicyclic result of Eroh et al.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03421594
Contributor : Quentin Deschamps Connect in order to contact the contributor
Submitted on : Tuesday, November 9, 2021 - 4:28:40 PM
Last modification on : Tuesday, November 16, 2021 - 3:56:29 AM

File

Metric dimension on sparse gra...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03421594, version 1

Citation

Nicolas Bousquet, Quentin Deschamps, Aline Parreau, Ignacio Pelayo. Metric dimension on sparse graphs and its applications to zero forcing sets. 2021. ⟨hal-03421594⟩

Share

Metrics

Les métriques sont temporairement indisponibles