Intermediate Minimal \(k\)-Rankings of Graphs

Abstract

Given a graph \( G \), a function \( f : V(G) \to \{1, 2, \ldots, 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) \leq k \leq \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.