Minimal k-rankings and the a-rank number of a path

Given a graph G, a function f: V(G) -\u3e {1, 2, ..., k} is a k-ranking of G if f(u) = f(v) implies every u - v path contains a vertex w such that f(w) \u3e f(u). A k-ranking is minimal if the reduction of any label greater than 1 violates the described ranking property. The a-rank number of G, denoted u,(G) equals the largest k such that G has a minimal k-ranking. We establish new results involving minimal rankings of paths and in particular we determine u(Pn), a problem suggested by Laskar and Pillone in 2000. We show u(Pn) = [log2 (n + 1)] + [log2(n + 1 - (2^([log2n]-1))] (Refer to PDF file for exact formulas)