Flanking Mumbers and Arankings of Cyclic Graphs

Abstract

Given a graph $G$, a $k$-ranking is a labeling of the vertices such that any path connecting two vertices with the same label contains a vertex with a larger label. A $k$-ranking is minimal if and only if reducing any label violates the ranking property. The arank number of a graph ${\psi }_r(G)$, is the maximum $k$ such that $G$ has a minimal $k$-ranking. The arank number of a cycle was first investigated by Kostyuk and Narayan. They determined precise arank numbers for most cycles, and determined the arank number within $1$ for all other cases. In this paper we introduce a new concept called the flanking number, which is used to solve all open cases. We prove that ${\psi }_r(C_n)=\lfloor {\log }_2(n+1)\rfloor +\lfloor {\log }_2\left(\frac{n+2}{3}\right)\rfloor +1$ for all $n>6$, which completely solves the problem that has been open since $2003$.