ARANKINGS OF TREES

For a graph G = (V, E), a function f : V(G) -> {1, 2, ... , k} is a k-ranking 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 chi(r)(G) and the arank number psi(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 psi(r) of a tree and shows the bound is sharp for perfect k-ary trees.