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 P2 × Pn. 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
@article{bwmeta1.element.doi-10_7151_dmgt_1739,
author = {Peter Richter and Emily Leven and Anh Tran and Bryan Ek and Jobby Jacob and Darren A. Narayan},
title = {Rank numbers for bent ladders},
journal = {Discussiones Mathematicae Graph Theory},
volume = {34},
year = {2014},
pages = {309-329},
zbl = {1290.05127},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1739}
}
Peter Richter; Emily Leven; Anh Tran; Bryan Ek; Jobby Jacob; Darren A. Narayan. Rank numbers for bent ladders. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 309-329. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1739/
[1] H. Alpert, Rank numbers of grid graphs, Discrete Math. 310 (2010) 3324-3333. doi:10.1016/j.disc.2010.07.022[Crossref] | 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[Crossref]
[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[Crossref]
[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[Crossref]
[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[Crossref]
[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[Crossref] | Zbl 0863.05071
[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[Crossref] | 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[Crossref] | 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[Crossref]
[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[WoS][Crossref]
[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[Crossref] | 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 [Crossref] | Zbl 0764.68132