# Rank numbers for bent ladders

Peter Richter; Emily Leven; Anh Tran; Bryan Ek; Jobby Jacob; Darren A. Narayan

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 2, page 309-329
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPeter Richter, et al. "Rank numbers for bent ladders." Discussiones Mathematicae Graph Theory 34.2 (2014): 309-329. <http://eudml.org/doc/267567>.

@article{PeterRichter2014,

abstract = {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},

author = {Peter Richter, Emily Leven, Anh Tran, Bryan Ek, Jobby Jacob, Darren A. Narayan},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph colorings; rankings of graphs; rank number; Cartesian product of graphs; ladder graph; bent ladder graph},

language = {eng},

number = {2},

pages = {309-329},

title = {Rank numbers for bent ladders},

url = {http://eudml.org/doc/267567},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Peter Richter

AU - Emily Leven

AU - Anh Tran

AU - Bryan Ek

AU - Jobby Jacob

AU - Darren A. Narayan

TI - Rank numbers for bent ladders

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 2

SP - 309

EP - 329

AB - 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

LA - eng

KW - graph colorings; rankings of graphs; rank number; Cartesian product of graphs; ladder graph; bent ladder graph

UR - http://eudml.org/doc/267567

ER -

## References

top- [1] H. Alpert, Rank numbers of grid graphs, Discrete Math. 310 (2010) 3324-3333. doi:10.1016/j.disc.2010.07.022[Crossref] Zbl1221.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] Zbl0863.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] Zbl0661.68063
- [8] R.E. Jamison, Coloring parameters associated with the rankings of graphs, Congr. Numer. 164 (2003) 111-127. Zbl1043.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] Zbl0842.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] Zbl1221.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] Zbl0764.68132

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.