Geodesic
Minimal rankings of the Cartesian product Kₙ ☐ Kₘ
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 725-735.

Voir la notice de l'article provenant de la source Library of Science

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, ψ_r(G), 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.
Keywords: graph colorings, rankings of graphs, minimal rankings, rank number, arank number, Cartesian product of graphs, rook's graph 
@article{DMGT_2012_32_4_a8,
     author = {Eyabi, Gilbert and Jacob, Jobby and Laskar, Renu and Narayan, Darren and Pillone, Dan},
     title = {Minimal rankings of the {Cartesian} product {Kₙ} ☐ {Kₘ}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {725--735},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a8/}
}
TY  - JOUR
AU  - Eyabi, Gilbert
AU  - Jacob, Jobby
AU  - Laskar, Renu
AU  - Narayan, Darren
AU  - Pillone, Dan
TI  - Minimal rankings of the Cartesian product Kₙ ☐ Kₘ
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 725
EP  - 735
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a8/
LA  - en
ID  - DMGT_2012_32_4_a8
ER  - 
%0 Journal Article
%A Eyabi, Gilbert
%A Jacob, Jobby
%A Laskar, Renu
%A Narayan, Darren
%A Pillone, Dan
%T Minimal rankings of the Cartesian product Kₙ ☐ Kₘ
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 725-735
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a8/
%G en
%F DMGT_2012_32_4_a8
Eyabi, Gilbert; Jacob, Jobby; Laskar, Renu; Narayan, Darren; Pillone, Dan. Minimal rankings of the Cartesian product Kₙ ☐ Kₘ. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 725-735. http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a8/

[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.

[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.

[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.

[4] J. Ghoshal, R. Laskar and D. Pillone, Minimal rankings, Networks 28 ( 1996) 45-53, doi: 10.1002/(SICI)1097-0037(199608)28:145::AID-NET6>3.0.CO;2-D

[5] J. Ghoshal, R. Laskar and D. Pillone, Further results on minimal rankings, Ars Combin. 52 (1999) 181-198.

[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.

[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.

[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.

[9] R. Laskar and D. Pillone, Theoretical and complexity results for minimal rankings, J. Combin. Inform. System Sci. 25) (2000) 17-33.

[10] R. Laskar and D. Pillone, Extremal results in rankings, Congr. Numer. 149 (2001) 33-54.

[11] C. Leiserson, Area efficient graph layouts for VLSI, Proc. 21st Ann IEEE Symp. FOCS (1980) 270-281.

[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.

[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.

[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.

[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.