Article in volume
Authors:
Title:
The threshold dimension and irreducible graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 195-210
Received: 2020-02-25 , Revised: 2020-08-24 , Accepted: 2020-08-24 , Available online: 2020-09-23 , https://doi.org/10.7151/dmgt.2359
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 $\beta(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 $\tau(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 $\beta(G) = \tau(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 \leq b < n$, there is an irreducible
graph of order $n$ and metric dimension $b$.
Keywords:
threshold dimension, metric dimension, distance in graphs
References:
- 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 - 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 - 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 - 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 - F. Harary and R. Melter, The metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
- 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 - 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 - 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 - I. Javaid, M.T. Rahim and K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 65 (2008) 21–33.
- 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 - 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.
- P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
Close