- Tytuł:
- Arankings of Trees
- Autorzy:
- Pillone, D.
- Powiązania:
- https://bibliotekanauki.pl/articles/31343445.pdf
- Data publikacji:
- 2019-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
minimal ranking
coloring
tree - Opis:
- For a graph G = (V, E), a function f : V (G) → {1, 2, . . ., k} is a kranking for G if f(u) = f(v) implies that every u − v path contains a vertex w such that f(w) > f(u). A minimal k-ranking, f, of a graph, G, is a k-ranking with the property that decreasing the label of any vertex results in the ranking property being violated. The rank number χr(G) and the arank number ψr(G) are, respectively, the minimum and maximum value of k such that G has a minimal k-ranking. This paper establishes an upper bound for ψr of a tree and shows the bound is sharp for perfect k-ary trees.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 2; 415-437
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł