×

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.)
PDFBibTeX XMLCite
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, (Graph-Theoretic Concepts in Computer Science (Herrsching, 1994). Graph-Theoretic Concepts in Computer Science (Herrsching, 1994), Lecture Notes in Comput. Sci., vol. 903 (1995), Springer: Springer Berlin), 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, (STACS 94. STACS 94, Caen, 1994. STACS 94. STACS 94, Caen, 1994, Lecture Notes in Comput. Sci., vol. 775 (1994), Springer: Springer Berlin), 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, (Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 164 (2003)), 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\); V. Kostyuk, D. Narayan, Maximum minimal \(k\) · 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, (Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, LA, 2001, vol. 149 (2001)), 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\); J. Ortiz, H. King, A. Zemke, D. Narayan, Minimal \(k\) · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.