Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21285120200601The 2-dimension of a Tree69811397910.22049/cco.2019.26495.1119ENJasonHedetniemiDepartment of Mathematics
Wingate University
Wingate NC
USAStephenHedetniemiSchool of Computing
Clemson University
Clemson, SC
U.S.A.Renu C.Renu C. LaskarClemson UniversityHenry MartynMulderEconometrisch Instituut
Erasmus Universiteit
Rotterdam
Netherlands0000-0002-4776-4046Journal Article20190523Let $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.http://comb-opt.azaruniv.ac.ir/article_13979_67e6ec33d043a864ea37af1094c77ac3.pdf