zbMATH — the first resource for mathematics

Maximum minimal \(k\)-rankings of cycles. (English) Zbl 1313.05322
Given a graph \(G\), a function \(f: V(G)\to \{1,2,\dots ,k\}\) is a \(k\)-ranking of \(G\) if \(f(u)=f(v)\) implies that every \(u-v\) path contains a vertex \(w\) such that \(f(w)>f(u)\). A \(k\)-ranking is minimal if the reduction of any label greater than 1 violates the ranking property. The arank number of \(G\), denoted \(\psi _r(G)\), is the maximum \(k\) such that \(G\) has a minimal \(k\)-ranking.
In [V. Kostyuk et al., Discrete Math. 306, No. 16, 1991–1996 (2006; Zbl 1101.05040)] it was proved that \(\psi _r(Pn)=\lfloor \log _2(n+1)\rfloor +\lfloor \log _2(n+1-(2^{\lfloor \log _2 n\rfloor }-1)) \rfloor \).
The authors prove that if \(m\leq n\), then \(\psi _r(C_m)\leq \psi _r(C_n)\) and show that for any \(n\geq 3\) either \(\psi _r(C_n)=\psi _r(P_n)\) or \(\psi _r(C_n)\leq \psi _r(P_n)+1\).

05C78 Graph labelling (graceful graphs, bandwidth, etc.)