×

Rank numbers for bent ladders. (English) Zbl 1290.05127

Summary: A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices with the same label contains a vertex with a larger label. The rank number of a graph is the fewest number of labels that can be used in a ranking. The rank number of a graph is known for many families, including the ladder graph \(P_{2}\times P_{n}\). We consider how “bending” a ladder affects the rank number. We prove that in certain cases the rank number does not change, and in others the rank number differs by only 1. We investigate the rank number of a ladder with an arbitrary number of bends.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C15 Coloring of graphs and hypergraphs
05C76 Graph operations (line graphs, products, etc.)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] H. Alpert, Rank numbers of grid graphs, Discrete Math. 310 (2010) 3324-3333. doi:10.1016/j.disc.2010.07.022 · Zbl 1221.05280
[2] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. M¨uller and Zs. Tuza, Rankings of graphs, SIAM J. Discrete Math. 11 (1998) 168-181. doi:10.1137/S0895480195282550
[3] E. Bruoth and M. Horˇn´ak, Online-ranking numbers for cycles and paths, Discuss. Math. Graph Theory 19 (1999) 175-197. doi:10.7151/dmgt.1094 · Zbl 0958.05076
[4] C.-W. Chang, D. Kuo and H-C. Lin, Ranking numbers of graphs, Inform. Process. Lett. 110 (2010) 711-716. doi:10.1016/j.ipl.2010.05.025 · Zbl 1233.05173
[5] D. Dereniowski, Rank coloring of graphs, in: Graph Colorings, M. Kubale (Ed.), Contemp. Math. AMS 352 (2004) 79-93. doi:10.1090/conm/352/06
[6] J. Ghoshal, R. Laskar, and D. Pillone, Minimal rankings, Networks 28 (1996) 45-53. doi:10.1002/(SICI)1097-0037(199608)28:1h45::AID-NET6i3.0.CO;2-D
[7] A.V. Iyer, H.D. Ratliff and G. Vijayan, Optimal node ranking of trees, Inform. Process. Lett. 28 (1988) 225-229. doi:10.1016/0020-0190(88)90194-9 · Zbl 0661.68063
[8] R.E. Jamison, Coloring parameters associated with the rankings of graphs, Congr. Numer. 164 (2003) 111-127. · Zbl 1043.05049
[9] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141-154. doi:10.1016/0012-365X(93)E0216-Q · Zbl 0842.05032
[10] T. Kloks, H. M¨uller and C.K. Wong, Vertex ranking of asteroidal triple-free graphs, Inform. Process. Lett. 68 (1998) 201-206. doi:10.1016/S0020-0190(98)00162-8 · Zbl 1339.05395
[11] C.E. Leiserson, Area efficient graph layouts for VLSI, Proc. 21st Ann. IEEE Symposium, FOCS (1980) 270-281.
[12] S. Novotny, J. Ortiz, and D.A. Narayan, Minimal k-rankings and the rank number of P2 n, Inform. Process. Lett. 109 (2009) 193-198. doi:10.1016/j.ipl.2008.10.004 · Zbl 1286.05050
[13] J. Ortiz, H. King, A. Zemke and D.A. Narayan, Minimal k-rankings for prism graphs, Involve 3 (2010) 183-190. doi:10.2140/involve.2010.3.183 · Zbl 1221.05159
[14] A. Sen, H. Deng and S. Guha, On a graph partition problem with application to VLSI Layout , Inform. Process. Lett. 43 (1992) 87-94. doi:10.1016/0020-0190(92)90017-P · Zbl 0764.68132
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.