# zbMATH — the first resource for mathematics

Minimal rankings. (English) Zbl 0863.05071
Summary: A $$k$$-ranking, $$f$$, for a graph $$G$$ is a function $$f:V(G) \to \{1,2, \dots, k\}$$ such that if $$u$$, $$v\in V(G)$$ and $$f(u) = f(v)$$, then every $$u$$–$$v$$ path contains a vertex $$w$$ such that $$f(w) > f(u)$$. We define minimal rankings of graphs. Properties of minimal rankings are established and then used to determine $$\chi_r$$, the minimum ranking number, and $$\psi_r$$, the maximum ranking number over all minimal rankings, for complete $$n$$-partite graphs and for split graphs.

##### MSC:
 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 05C35 Extremal problems in graph theory
Full Text: