×

Rank numbers of grid graphs. (English) Zbl 1221.05280

Summary: A ranking of a graph is a labeling of the vertices with positive integers such that any path between vertices of the same label contains a vertex of greater label. The rank number of a graph is the smallest possible number of labels in a ranking. We find rank numbers of the Möbius ladder, \(K_s \times P_n\), and \(P_{3}\times P_n\). We also find bounds for rank numbers of general grid graphs \(P_m \times P_n\).

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Bodlaender, H.L.; Deogun, J.S.; Jansen, K.; Kloks, T.; Kratsch, D.; Müller, H.; Tuza, Zs., Rankings of graphs, (), 292-304
[2] Bodlaender, H.L.; Deogun, J.S.; Jansen, K.; Kloks, T.; Kratsch, D.; Müller, H.; Tuza, Zs., Rankings of graphs, SIAM J. discrete math., 11, 1, 168-181, (1998), (electronic) · Zbl 0907.68137
[3] Chang, C.-W.; Kuo, D.; Lin, H.-C., Ranking numbers of graphs, Inform. process. lett., 110, 16, 711-716, (2010) · Zbl 1233.05173
[4] Deogun, J.S.; Kloks, T.; Kratsch, D.; Müller, H., On vertex ranking for permutation and other graphs, (), 747-758 · Zbl 0941.05516
[5] Deogun, J.S.; Kloks, T.; Kratsch, D.; Müller, H., On the vertex ranking problem for trapezoid, circular-arc and other graphs, Discrete appl. math., 98, 1-2, 39-63, (1999) · Zbl 0937.68093
[6] Dereniowski, D.; Nadolski, A., Vertex rankings of chordal graphs and weighted trees, Inform. process. lett., 98, 3, 96-100, (2006) · Zbl 1187.68340
[7] Ghoshal, J.; Laskar, R.; Pillone, D., Minimal rankings, Networks, 28, 1, 45-53, (1996) · Zbl 0863.05071
[8] Ghoshal, J.; Laskar, R.; Pillone, D., Further results on minimal rankings, Ars combin., 52, 181-198, (1999) · Zbl 0977.05048
[9] Hsieh, S., On vertex ranking of a starlike graph, Inform. process. lett., 82, 3, 131-135, (2002) · Zbl 1013.68141
[10] Hung, R., Optimal vertex ranking of block graphs, Inform. and comput., 206, 11, 1288-1302, (2008) · Zbl 1169.68038
[11] Isaak, G.; Jamison, R.; Narayan, D., Greedy rankings and arank numbers, Inform. process. lett., 109, 15, 825-827, (2009) · Zbl 1197.05144
[12] Iyer, A.V.; Ratliff, H.D.; Vijayan, G., Optimal node ranking of trees, Inform. process. lett., 28, 5, 225-229, (1988) · Zbl 0661.68063
[13] Jamison, R., Coloring parameters associated with rankings of graphs, (), 111-127 · Zbl 1043.05049
[14] Kloks, T.; Müller, H.; Wong, C.K., Vertex ranking of asteroidal triple-free graphs, Inform. process. lett., 68, 4, 201-206, (1998) · Zbl 1339.05395
[15] V. Kostyuk, D. Narayan, Maximum minimal \(k\)-rankings of cycles, Ars Combin. (2009) (in press). · Zbl 1313.05322
[16] Kostyuk, V.; Narayan, D.; Williams, V., Minimal rankings and the arank number of a path, Discrete math., 306, 16, 1991-1996, (2006) · Zbl 1101.05040
[17] Laskar, R.; Pillone, D., Theoretical and complexity results for minimal rankings, J. combin. inform. system sci., 25, 1-4, 17-33, (2000), Recent advances in interdisciplinary mathematics (Portland, ME, 1997) · Zbl 1219.05188
[18] Laskar, R.; Pillone, D., Extremal results in rankings, (), 33-54 · Zbl 0989.05058
[19] Liu, C.; Yu, M., An optimal parallel algorithm for node ranking of cographs, Discrete appl. math., 87, 1-3, 187-201, (1998) · Zbl 0906.68087
[20] Novotny, S.; Ortiz, J.; Narayan, D., Minimal \(k\)-rankings and the rank number of \(P_n^2\), Inform. process. lett., 109, 3, 193-198, (2009) · Zbl 1286.05050
[21] J. Ortiz, H. King, A. Zemke, D. Narayan, Minimal \(k\)-rankings of prism graphs, Involve (2009) (in press). · Zbl 1221.05159
[22] Schäffer, A., Optimal node ranking of trees in linear time, Inform. process. lett., 33, 2, 91-96, (1989) · Zbl 0683.68038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.