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.

, , , ,
doi.org/10.22049/CCO.2019.26495.1119, hdl.handle.net/1765/132161
Communications in Combinatorics and Optimization
Department of Econometrics

Hedetniemi, J.T. (Jason T.), Hedetniemi, S.T. (Stephen T.), Laskar, R. C., & Mulder, M. (2020). The 2-dimension of a tree. Communications in Combinatorics and Optimization, 5(1), 69–81. doi:10.22049/CCO.2019.26495.1119