For a graph G = (V, E), a function f:V(G) → 1,2, ...,k is a k-ranking if f(u) = f(v) implies that every u - v path contains a vertex w such that f(w) > f(u). A k-ranking is minimal if decreasing any label violates the definition of ranking. The arank number, , of G is the maximum value of k such that G has a minimal k-ranking. We completely determine the arank number of the Cartesian product Kₙ ☐ Kₙ, and we investigate the arank number of Kₙ ☐ Kₘ where n > m.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1634,
author = {Gilbert Eyabi and Jobby Jacob and Renu C. Laskar and Darren A. Narayan and Dan Pillone},
title = {Minimal rankings of the Cartesian product Kn Km},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {725-735},
zbl = {1293.05334},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1634}
}
Gilbert Eyabi; Jobby Jacob; Renu C. Laskar; Darren A. Narayan; Dan Pillone. Minimal rankings of the Cartesian product Kₙ ☐ Kₘ. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 725-735. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1634/
[000] [1] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller and Zs. Tuza, Rankings of graphs, Graph-theoretic concepts in computer science (Herrsching, 1994), Lect. Notes Comput. Sci. 903 (1995) 292-304.
[001] [2] P.De la Torre, R. Greenlaw and A. Schaeffer, Optimal ranking of trees in polynomial time, In: Proc. 4^{th} ACM Symp. on Discrete Algorithms, Austin Texas, (1993) 138-144. | Zbl 0801.68129
[002] [3] I.S. Duff and J.K. Reid, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software (1983) 9 302-325, doi: 10.1145/356044.356047. | Zbl 0515.65022
[003] [4] J. Ghoshal, R. Laskar and D. Pillone, Minimal rankings, Networks 28 ( 1996) 45-53, doi: 10.1002/(SICI)1097-0037(199608)28:1<45::AID-NET6>3.0.CO;2-D | Zbl 0863.05071
[004] [5] J. Ghoshal, R. Laskar and D. Pillone, Further results on minimal rankings, Ars Combin. 52 (1999) 181-198. | Zbl 0977.05048
[005] [6] S. Hsieh, On vertex ranking of a starlike graph, Inform. Process. Lett. 82 (2002) 131-135, doi: 10.1016/S0020-0190(01)00262-9.
[006] [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. | Zbl 0661.68063
[007] [8] V. Kostyuk, D.A. Narayan and V.A. Williams, Minimal rankings and the arank number of a path, Discrete Math. 306 (2006) 1991-1996, doi: 10.1016/j.disc.2006.01.027. | Zbl 1101.05040
[008] [9] R. Laskar and D. Pillone, Theoretical and complexity results for minimal rankings, J. Combin. Inform. System Sci. 25) (2000) 17-33. | Zbl 1219.05188
[009] [10] R. Laskar and D. Pillone, Extremal results in rankings, Congr. Numer. 149 (2001) 33-54. | Zbl 0989.05058
[010] [11] C. Leiserson, Area efficient graph layouts for VLSI, Proc. 21st Ann IEEE Symp. FOCS (1980) 270-281.
[011] [12] J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl. 11 (1990) 134-172, doi: 10.1137/0611010. | Zbl 0697.65013
[012] [13] S. Novotny, J. Ortiz and D.A. Narayan, Minimal k-rankings and the rank number of P²ₙ, Inform. Process. Lett. 109 (2009) 193-198, doi: 10.1016/j.ipl.2008.10.004. | Zbl 1286.05050
[013] [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. | Zbl 0764.68132
[014] [15] X. Zhou, N. Nagai and T. Nishizeki, Generalized vertex-rankings of trees, Inform. Process. Lett. 56 (1995) 321-328, doi: 10.1016/0020-0190(95)00172-7.