Rank numbers for bent ladders

• Autorzy: Peter Richter , Emily Leven , Anh Tran , Bryan Ek , Jobby Jacob , Darren A. Narayan
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

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

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 2
• Strony: 309-329

Daty

wydano

2014-05-01

online

2014-04-12

Twórcy

autor

Peter Richter

• Department of Mathematics, University of Rochester Rochester, NY 14642-0002, USA

autor

Emily Leven

• Department of Mathematics, University of California San Diego, La Jolla, California, 92093-0112, USA

autor

Anh Tran

• Department of Mathematics, Temple University Philadelphia PA 19122, USA

autor

Bryan Ek

• School of Mathematical Sciences Rochester Institute of Technology Rochester, NY 14623, USA

autor

Jobby Jacob

• School of Mathematical Sciences Rochester Institute of Technology Rochester, NY 14623, USA

autor

Darren A. Narayan

• School of Mathematical Sciences Rochester Institute of Technology Rochester, NY 14623, USA

Bibliografia

• [1] H. Alpert, Rank numbers of grid graphs, Discrete Math. 310 (2010) 3324-3333. doi:10.1016/j.disc.2010.07.022[Crossref]
• [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]
• [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]
• [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[Crossref]
• [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]
• [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]

Identyfikatory

DOI

10.7151/dmgt.1739