1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The Threshold Dimension and Irreducible Graphs

Published Online: 20 Oct 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 25 Feb 2020
Accepted: 24 Aug 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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(log2n). 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 < n, there is an irreducible graph of order n and metric dimension b.

Keywords

MSC 2010

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

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

[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. doi:10.1137/05064186710.1137/050641867Search in Google Scholar

[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. doi:10.1016/S0166-218X(00)00198-010.1016/S0166-218X(00)00198-0Search in Google Scholar

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

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

[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. doi:10.1016/j.endm.2005.06.02310.1016/j.endm.2005.06.023Search in Google Scholar

[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. doi:10.37236/30210.37236/302Search in Google Scholar

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

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

[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.Search in Google Scholar

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo