Greedy rankings and arank numbers
A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices of the same rank contains a vertex of strictly larger rank. A ranking is locally minimal if reducing the rank of any single vertex produces a non-ranking. A ranking is globally minimal if reducing the ranks of any set of vertices produces a non-ranking. A ranking is greedy if, for some ordering of the vertices, it is the ranking produced by assigning ranks in that order, always selecting the smallest possible rank. We will show that these three notions are equivalent. If a ranking satisfies one property it satisfies all three. As a consequence of this and known results on arank numbers of paths we improve known upper bounds for on-line ranking of paths and cycles. (C) 2009 Elsevier B.V. All rights reserved.
graph algorithms vertex coloring on-line ranking number rank number minimal rankings