×

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
PDF BibTeX XML Cite
Full Text: DOI