# 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$$.

##### MSC:
 05C78 Graph labelling (graceful graphs, bandwidth, etc.)
##### Keywords:
$$k$$-ranking of graphs; arank number