The 2-dimension of a Tree
Autor: | Jason T. Hedetniemi, Stephen T. Hedetniemi, Renu C. Laskar, Henry Martyn Mulder |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2020 |
Předmět: | |
Zdroj: | Communications in Combinatorics and Optimization, Vol 5, Iss 1, Pp 69-81 (2020) |
Druh dokumentu: | article |
ISSN: | 2538-2128 2538-2136 |
DOI: | 10.22049/CCO.2019.26495.1119 |
Popis: | 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. |
Databáze: | Directory of Open Access Journals |
Externí odkaz: |