PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 2 | 309-329
Tytuł artykułu

Rank numbers for bent ladders

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
34
Numer
2
Strony
309-329
Opis fizyczny
Daty
wydano
2014-05-01
online
2014-04-12
Twórcy
autor
  • Department of Mathematics, University of California San Diego, La Jolla, California, 92093-0112, USA, esergel07@gmail.com
autor
autor
  • School of Mathematical Sciences Rochester Institute of Technology Rochester, NY 14623, USA, bte1759@rit.edu
autor
  • School of Mathematical Sciences Rochester Institute of Technology Rochester, NY 14623, USA, jxjsma@rit.edu
  • School of Mathematical Sciences Rochester Institute of Technology Rochester, NY 14623, USA, dansma@rit.edu
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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1739
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.