Geodesic
The threshold dimension and irreducible graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 195-210

Voir la notice de l'article provenant de la source Library of Science

Let G be a graph, and let u, v, and w be vertices of G. If the distance between u and w does not equal the distance between v and w, then w is said to resolve u and v. The metric dimension of G, denoted β(G), is the cardinality of a smallest set W of vertices such that every pair of vertices of G is resolved by some vertex of W. The threshold dimension of G, denoted τ(G), is the minimum metric dimension among all graphs H having G as a spanning subgraph. In other words, the threshold dimension of G is the minimum metric dimension among all graphs obtained from G by adding edges. If β(G) = τ(G), then G is said to be irreducible. We give two upper bounds for the threshold dimension of a graph, the first in terms of the diameter, and the second in terms of the chromatic number. As a consequence, we show that every planar graph of order n has threshold dimension O (log_2 n). We show that several infinite families of graphs, known to have metric dimension 3, are in fact irreducible. Finally, we show that for any integers n and b with 1 ≤ b lt; n, there is an irreducible graph of order n and metric dimension b.
Keywords: threshold dimension, metric dimension, distance in graphs 
@article{DMGT_2023_43_1_a12,
     author = {Mol, Lucas and Murphy, Matthew J. H. and Oellermann, Ortrud R.},
     title = {The threshold dimension and irreducible graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {195--210},
     publisher = {mathdoc},
     volume = {43},
     number = {1},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a12/}
}
TY  - JOUR
AU  - Mol, Lucas
AU  - Murphy, Matthew J. H.
AU  - Oellermann, Ortrud R.
TI  - The threshold dimension and irreducible graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 195
EP  - 210
VL  - 43
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a12/
LA  - en
ID  - DMGT_2023_43_1_a12
ER  - 
%0 Journal Article
%A Mol, Lucas
%A Murphy, Matthew J. H.
%A Oellermann, Ortrud R.
%T The threshold dimension and irreducible graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 195-210
%V 43
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a12/
%G en
%F DMGT_2023_43_1_a12
Mol, Lucas; Murphy, Matthew J. H.; Oellermann, Ortrud R. The threshold dimension and irreducible graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 195-210. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a12/