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

Abstract

top
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

How to cite

top

Peter 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. [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. [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. [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. [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. [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. [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. [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. [8] R.E. Jamison, Coloring parameters associated with the rankings of graphs, Congr. Numer. 164 (2003) 111-127. Zbl1043.05049
  9. [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. [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. [11] C.E. Leiserson, Area efficient graph layouts for VLSI, Proc. 21st Ann. IEEE Symposium, FOCS (1980) 270-281. 
  12. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.