期刊论文详细信息
Discussiones Mathematicae Graph Theory | |
Arankings of Trees | |
Pillone D.1  | |
[1] Brielle, N.J., USA; | |
关键词: minimal ranking; coloring; tree; 05c15; 05c05; | |
DOI : 10.7151/dmgt.2090 | |
来源: DOAJ |
【 摘 要 】
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.
【 授权许可】
Unknown