Geodesic
The threshold dimension and irreducible graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 195-210 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2023},
     volume = {43},
     number = {1},
     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
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
%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/

[1] R. Belmonte, F.V. Fomin, P.A. Golovach and M.S. Ramanujan, Metric dimension of bounded width graphs, in: Mathematical Foundations of Computer Science 2015 (MFCS 2015), Lecture Notes in Comput. Sci. 9235, G. Italiano, G. Pighizzini, and D. Sannella (Ed(s)), (Springer, Berlin, Heidelberg 2015) 115–126. https://doi.org/10.1007/978-3-662-48054-0_10

[2] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (SIAM Monographs on Discrete Mathematics and Applications, 1999). https://doi.org/10.1137/1.9780898719796

[3] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara and D.R. Wood, On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math. 21 (2007) 423–441. https://doi.org/10.1137/050641867

[4] G. Chartrand, L. Eroh, M.A. Johnson and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000)) 99–113. https://doi.org/10.1016/S0166-218X(00)00198-0

[5] F. Harary and R. Melter, The metric dimension of a graph, Ars Combin. 2 (1976) 191–195.

[6] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229. https://doi.org/10.1016/0166-218X(95)00106-2

[7] C. Hernando, M. Mora, I.M. Pelayo, C. Seara, J. Cáceres and M.L. Puertas, On the metric dimension of some families of graphs, Electron. Notes Discrete Math. 22 (2005) 129–133. https://doi.org/10.1016/j.endm.2005.06.023

[8] C. Hernando, M. Mora, I.M. Pelayo, C. Seara and D.R. Wood, Extremal graph theory for metric dimension and diameter, Electron. J. Combin. 17 (2010) #R30. https://doi.org/10.37236/302

[9] I. Javaid, M.T. Rahim and K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 65 (2008) 21–33.

[10] L. Mol, M.J.H. Murphy and O.R. Oellermann, The threshold dimension of a graph, Discrete Appl. Math. 287 (2020) 118–133. https://doi.org/10.1016/j.dam.2020.08.007

[11] G. Sudhakara and A.R. Hemanth Kumar, Graphs with metric dimension two–-a characterization, World Academy of Science, Engineering and Technology 36 (2009) 622–627.

[12] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.