Journal Details Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English Open Access

# The Threshold Dimension and Irreducible Graphs

###### Accepted: 24 Aug 2020
Journal Details Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

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.

#### MSC 2010

 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

 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

 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

 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

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

 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

 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

 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

 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

 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

 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

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

• #### A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD