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