Intermediate Minimal $k$-Rankings of Graphs

Abstract

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 every $u$-$v$ path contains a vertex $w$ such that $f(w)>f(u)$. A $k$-ranking is \emph{minimal} if the reduction of any label greater than $1$ violates the described ranking property. The rank number of a graph, denoted ${\chi }_r(G)$, is the minimum $k$ such that $G$ has a minimal $k$-ranking. The arank number of a graph, denoted ${\psi }_r(G)$, is the maximum $k$ such that $G$ has a minimal $k$-ranking. It was asked by Laskar, Pillone, Eyabi, and Jacob if there is a family of graphs where minimal $k$-rankings exist for all ${\chi }_r(G)\le k\le {\psi }_r(G)$. We give an affirmative answer showing that all intermediate minimal $k$-rankings exist for paths and cycles. We also give a characterization of all complete multipartite graphs which have this intermediate ranking property and which do not.