Arankings of Trees

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.