Minimal rankings of the Cartesian product \(K_n \square K_m\). (English) Zbl 1293.05334

Summary: For a graph \(G = (V, E)\), a function \(f:V(G)\to \{1,2,\dots,k\}\) is a \(k\)-ranking 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 decreasing any label violates the definition of ranking. The arank number, \(\phi_r(G)\), of \(G\) is the maximum value of \(k\) such that \(G\) has a minimal \(k\)-ranking. We completely determine the arank number of the Cartesian product \(K_n\square K_n\), and we investigate the arank number of \(K_n\square K_m\) where \(n > m\).


05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C15 Coloring of graphs and hypergraphs
05C76 Graph operations (line graphs, products, etc.)
Full Text: DOI