Theoretical and complexity results for minimal rankings. (English) Zbl 1219.05188

Laskar, R.; Pillone, D.

J. Comb. Inf. Syst. Sci. 25, No. 1-4, 17-33 (2000).

Let \(G\) be a graph. A function \(f\): V(G)\to{1,2,…,k}\( is a \)k\(-ranking for \)G\( if \)f(u)=f(v)\( implies that every \)u\(-\)v\( path \)P\( contains a vertex \)w\( such that \)f(w)>f(u)\(. A function \)f\colon V(G)\to{1,2,…,k}\( is a minimal \)k\(-ranking if \)f\( is a \)k\(-ranking and for any \)x\( such that \)f(x)>1\( a function \)g\( such that \)g(z)=f(z)\( for \)z\neq x\( and \)1\leq g(x)<f(x)\( is not a \)k\(-ranking. This paper examines some theoretical aspects of minimal rankings and shows that the decision problem corresponding to minimal rankings is NP-complete.\)

MSC:

05C85	Graph algorithms (graph-theoretic aspects)
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)