Further Results on Minimal Rankings

Let \(G\) be a graph. A function \(f: V(G) \to \{1, 2, \ldots, k\}\) is a \(k\)-ranking for \(G\) if \(f(u) = f(v)\) implies that every \(u-v\) path \(P\) contains a vertex \(w\) such that \(f(w) > f(u)\). A function \(f: V(G) \to \{1, 2, \ldots, 4\}\) is a minimal \(k\)-ranking if \(f\) is a \(k\)-ranking and for any \(x\) such that \(f(x) > 1\) the function \(g(z) = f(z)\) for \(z \neq x\) and \(1 \leq g(x) < f(x)\) is not a \(k\)-ranking. This paper establishes further properties of minimal rankings, gives a procedure for constructing minimal rankings, and determines, for some classes of graphs, the minimum value and maximum value of \(k\) for which \(G\) has a minimal \(k\)-ranking. In addition, we establish tighter bounds for the minimum value of \(k\) for which \(G\) has a \(k\)-ranking.