# zbMATH — the first resource for mathematics

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.

##### MSC:
 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
Full Text:
##### References:
  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  P. Curran, D.A. Narayan, Minimal rankings for catepillars and subclasses of trees, preprint.  de la Torre, P.; Greenlaw, R.; Przytycka, T., Optimal tree ranking is in NC, Parallel process. lett., 2, 1, 31-41, (1992)  M.J. Fisher, V. Kostyuk, D.A. Narayan, Minimal rankings of cycles, preprint. · Zbl 1313.05322  Ghoshal, J.; Laskar, R.; Pillone, D., Minimal rankings, Networks, 28, 45-53, (1996) · Zbl 0863.05071  Ghoshal, J.; Laskar, R.; Pillone, D., Further results on minimal rankings, Ars combin., 52, 181-198, (1999) · Zbl 0977.05048  Hsieh, S., On vertex ranking of a starlike graph, Inform. process. lett., 82, 131-135, (2002) · Zbl 1013.68141  Jamison, R.E., Coloring parameters associated with the rankings of graphs, Congr. numer., 164, 111-127, (2003) · Zbl 1043.05049  Laskar, R.; Pillone, D., Theoretical and complexity results for minimal rankings, J. combin. inform. sci., 25, 1-4, 17-33, (2000) · Zbl 1219.05188  Laskar, R.; Pillone, D., Extremal results in rankings, Congr. numer., 149, 33-54, (2001) · Zbl 0989.05058  C.E. Leiserson, Area efficient graph layouts for VLSI, Proceedings of the 21st Annual IEEE Symposium, FOCS, 1980, pp. 270-281.  D.A. Narayan, Minimal rankings of directed graphs, preprint. · Zbl 1234.05203  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  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.