Geodesic
Rank numbers for bent ladders
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 309-329.

Voir la notice de l'article provenant de la source Library of Science

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 × 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
Keywords: graph colorings, rankings of graphs, rank number, Cartesian product of graphs, ladder graph, bent ladder graph 
@article{DMGT_2014_34_2_a7,
     author = {Richter, Peter and Leven, Emily and Tran, Anh and Ek, Bryan and Jacob, Jobby and Narayan, Darren A.},
     title = {Rank numbers for bent ladders},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {309--329},
     publisher = {mathdoc},
     volume = {34},
     number = {2},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a7/}
}
TY  - JOUR
AU  - Richter, Peter
AU  - Leven, Emily
AU  - Tran, Anh
AU  - Ek, Bryan
AU  - Jacob, Jobby
AU  - Narayan, Darren A.
TI  - Rank numbers for bent ladders
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 309
EP  - 329
VL  - 34
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a7/
LA  - en
ID  - DMGT_2014_34_2_a7
ER  - 
%0 Journal Article
%A Richter, Peter
%A Leven, Emily
%A Tran, Anh
%A Ek, Bryan
%A Jacob, Jobby
%A Narayan, Darren A.
%T Rank numbers for bent ladders
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 309-329
%V 34
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a7/
%G en
%F DMGT_2014_34_2_a7
Richter, Peter; Leven, Emily; Tran, Anh; Ek, Bryan; Jacob, Jobby; Narayan, Darren A. Rank numbers for bent ladders. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 309-329. http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a7/

[1] H. Alpert, Rank numbers of grid graphs, Discrete Math. 310 (2010) 3324-3333. doi:10.1016/j.disc.2010.07.022

[2] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller and Zs. Tuza, Rankings of graphs, SIAM J. Discrete Math. 11 (1998) 168-181. doi:10.1137/S0895480195282550

[3] E. Bruoth and M. Horňák, Online-ranking numbers for cycles and paths, Discuss. Math. Graph Theory 19 (1999) 175-197. doi:10.7151/dmgt.1094

[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

[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

[8] R.E. Jamison, Coloring parameters associated with the rankings of graphs, Congr. Numer. 164 (2003) 111-127.

[9] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141-154. doi:10.1016/0012-365X(93)E0216-Q

[10] T. Kloks, H. Müller 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

[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 $P_n^2$, Inform. Process. Lett. 109 (2009) 193-198. doi:10.1016/j.ipl.2008.10.004

[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

[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