zbMATH — the first resource for mathematics

Greedy rankings and arank numbers. (English) Zbl 1197.05144
Summary: A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices of the same rank contains a vertex of strictly larger rank. A ranking is locally minimal if reducing the rank of any single vertex produces a non-ranking. A ranking is globally minimal if reducing the ranks of any set of vertices produces a non-ranking. A ranking is greedy if, for some ordering of the vertices, it is the ranking produced by assigning ranks in that order, always selecting the smallest possible rank. We will show that these three notions are equivalent. If a ranking satisfies one property it satisfies all three. As a consequence of this and known results on arank numbers of paths we improve known upper bounds for on-line ranking of paths and cycles.

05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI
[1] Bruoth, E.; Horňák, M., On-line ranking number for cycles and paths, Discuss. math. graph theory, 19, 175-197, (1999) · Zbl 0958.05076
[2] Bruoth, E.; Horňák, M., A lower bound for on-line ranking number of a path, Discrete math., 307, 1347-1355, (2007) · Zbl 1115.05047
[3] Erdos, P.; Hare, W.R.; Hedetniemi, S.T.; Laskar, R., On the equality of the Grundy and ochromatic numbers of a graph, J. graph theory, 11, 157-159, (1987) · Zbl 0708.05021
[4] Ghoshal, J.; Laskar, R.; Pillone, D., Minimal rankings, Networks, 28, 45-53, (1996) · Zbl 0863.05071
[5] Iyer, A.; Ratliff, H.D.; Vijayan, G., Optimal node ranking of trees, Inform. process. lett., 28, 225-229, (1988) · Zbl 0661.68063
[6] Jamison, R.E., Coloring parameters associated with rankings of graphs, Congr. numer., 164, 111-127, (2003) · Zbl 1043.05049
[7] R.E. Jamison, On the ranking poset of a graph, unpublished manuscript
[8] V. Kostyuk, D.A. Narayan, Maximum minimal rankings of cycles, Ars Combinatoria, in press · Zbl 1313.05322
[9] Kostyuk, V.; Narayan, D.A.; Williams, V.A., Minimal rankings and the arank number of a path, Discrete math., 306, 1991-1996, (2006) · Zbl 1101.05040
[10] Zs. Tuza, M. Voigt, Ranking problems on graphs, Manuscript, 1995 · Zbl 0991.05046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.