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: |
|