The 2-dimension of a Tree

Document Type : Original paper

Authors

1 Department of Mathematics Wingate University Wingate NC USA

2 School of Computing Clemson University Clemson, SC U.S.A.

3 Clemson University

4 Econometrisch Instituut Erasmus Universiteit Rotterdam Netherlands

Abstract

Let $x$ and $y$ be two distinct vertices in a connected graph $G$. The $x,y$-location of a vertex $w$ is the ordered pair of distances from $w$ to $x$ and $y$, that is, the ordered pair $(d(x,w), d(y,w))$. A set of vertices $W$ in $G$ is $x,y$-located if any two vertices in $W$ have distinct $x,y$-locations. A set $W$ of vertices in $G$ is 2-located if it is $x,y$-located, for some distinct vertices $x$ and $y$. The 2-dimension of $G$ is the order of a largest set that is 2-located in $G$. Note that this notion is related to the metric dimension of a graph, but not identical to it. We study in depth the trees $T$ that have a 2-locating set, that is, have 2-dimension equal to the order of $T$. Using these results, we have a nice characterization of the 2-dimension of arbitrary trees.

Keywords

Main Subjects

References

[1] 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), no. 1-3, 99–113.
[2] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
[3] S.T. Hedetniemi, R.C. Laskar, and H.M. Mulder, New resolvability parameters of graphs, submitted.
[4] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559. 
 
Communications in Combinatorics and Optimization
Volume 5, Issue 1
June 2020
Pages 69-81

Files

Share

How to cite

Statistics