Minimal rankings and the arank number of a path (Q2501577): Difference between revisions

A \(k\)-ranking of a graph \(G=(V,E)\) is a surjective colouring \(c : V \to \{1,2,\dots,k\}\) such that each \(u\)--\(w\)-path with \(c(u) = c(w)\) contains an internal vertex \(v\) with \(c(v) > c(u)\). A \(k\)-ranking is minimal if the reduction of any colour greater than \(1\) violates this ranking property. The arank number \(\psi_{\text r}(G)\) is the maximum value of \(k\) such that \(G\) has a minimal \(k\)-ranking, see e.g.\ \textit{J. Ghoshal, R. Laskar} and \textit{D. Pillone} [Ars Comb.\ 52, 181--198 (1999; Zbl 0977.05048)]. This note shows \(\psi_{\text r}(P_s) = 2m-2\) for all \(s \geq 2\) with \(2^m - 2^{m-2} - 1 \leq s \leq 2^m - 2\), and \(\psi_{\text r}(P_t) = 2m-1\) for all \(t \geq 2\) with \(2^m - 1 \leq t \leq 2^{m+1} - 2^{m-1} - 2\), where \(P_n\) denotes the path on \(n\) vertices.