Minimal k-rankings and the rank number of P_n²

Darren Narayan

ABSTRACT: For a graph G, a k-ranking is a labeling of the vertices using integers between 1 and k inclusive such that whenever there are two vertices with the same label, every path connecting them contains a vertex of higher label. A ranking is minimal if the reduction of any label results in a violation of the above ranking property. The rank number of a graph is the minimum k that can occur in a minimal ranking. The arank number is the maximum k that can appear in a minimum ranking. We investigate rank and arank numbers for paths, cycles and related graph families.