The 2-dimension of a tree
Communications in Combinatorics and Optimization , Volume 5 - Issue 1 p. 69- 81
Let x and y be two distinct vertices in a connected graph G. The x, ylocation 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.
|, , , ,|
|Communications in Combinatorics and Optimization|
|Organisation||Department of Econometrics|
Hedetniemi, J.T. (Jason T.), Hedetniemi, S.T. (Stephen T.), Laskar, R.C, & Mulder, H.M. (2020). The 2-dimension of a tree. Communications in Combinatorics and Optimization, 5(1), 69–81. doi:10.22049/CCO.2019.26495.1119