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

Eyabi, Gilbert; Jacob, Jobby; Laskar, Renu C.; Narayan, Darren A.; Pillone, Dan

Discuss. Math., Graph Theory 32, No. 4, 725-735 (2012).

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\).

MSC:

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

Keywords:

graph colorings; rankings of graphs; minimal rankings; rank number; arank number; Cartesian product of graphs; rook’s graph