Minimal rankings and the arank number of a path. (English) Zbl 1101.05040

A \(k\)-ranking of a graph \(G=(V,E)\) is a surjective colouring \(c : V \to \{1,2,\dots,k\}\) such that each \(u\)–\(w\)-path with \(c(u) = c(w)\) contains an internal vertex \(v\) with \(c(v) > c(u)\). A \(k\)-ranking is minimal if the reduction of any colour greater than \(1\) violates this ranking property. The arank number \(\psi_{\text r}(G)\) is the maximum value of \(k\) such that \(G\) has a minimal \(k\)-ranking, see e.g. J. Ghoshal, R. Laskar and D. Pillone [Ars Comb. 52, 181–198 (1999; Zbl 0977.05048)].
This note shows \(\psi_{\text r}(P_s) = 2m-2\) for all \(s \geq 2\) with \(2^m - 2^{m-2} - 1 \leq s \leq 2^m - 2\), and \(\psi_{\text r}(P_t) = 2m-1\) for all \(t \geq 2\) with \(2^m - 1 \leq t \leq 2^{m+1} - 2^{m-1} - 2\), where \(P_n\) denotes the path on \(n\) vertices.


05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C78 Graph labelling (graceful graphs, bandwidth, etc.)


vertex ranking


Zbl 0977.05048
Full Text: DOI


[1] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller, Z. Tuza, Rankings of graphs, Siam J. Discrete Math. 11(1), 168-181. · Zbl 0907.68137
[2] P. Curran, D.A. Narayan, Minimal rankings for catepillars and subclasses of trees, preprint.
[3] de la Torre, P.; Greenlaw, R.; Przytycka, T., Optimal tree ranking is in NC, Parallel process. lett., 2, 1, 31-41, (1992)
[4] M.J. Fisher, V. Kostyuk, D.A. Narayan, Minimal rankings of cycles, preprint. · Zbl 1313.05322
[5] Ghoshal, J.; Laskar, R.; Pillone, D., Minimal rankings, Networks, 28, 45-53, (1996) · Zbl 0863.05071
[6] Ghoshal, J.; Laskar, R.; Pillone, D., Further results on minimal rankings, Ars combin., 52, 181-198, (1999) · Zbl 0977.05048
[7] Hsieh, S., On vertex ranking of a starlike graph, Inform. process. lett., 82, 131-135, (2002) · Zbl 1013.68141
[8] Jamison, R.E., Coloring parameters associated with the rankings of graphs, Congr. numer., 164, 111-127, (2003) · Zbl 1043.05049
[9] Laskar, R.; Pillone, D., Theoretical and complexity results for minimal rankings, J. combin. inform. sci., 25, 1-4, 17-33, (2000) · Zbl 1219.05188
[10] Laskar, R.; Pillone, D., Extremal results in rankings, Congr. numer., 149, 33-54, (2001) · Zbl 0989.05058
[11] C.E. Leiserson, Area efficient graph layouts for VLSI, Proceedings of the 21st Annual IEEE Symposium, FOCS, 1980, pp. 270-281.
[12] D.A. Narayan, Minimal rankings of directed graphs, preprint. · Zbl 1234.05203
[13] Sen, A.; Deng, H.; Guha, S., On a graph partition problem with application to VLSI layouts, Inform. process. lett., 43, 87-94, (1992) · Zbl 0764.68132
[14] West, D.B., Introduction to graph theory, (2001), Prentice-Hall Englewood Cliffs, NJ
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.