# Minimal rankings of the Cartesian product Kₙ ☐ Kₘ

Gilbert Eyabi; Jobby Jacob; Renu C. Laskar; Darren A. Narayan; Dan Pillone

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 4, page 725-735
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGilbert Eyabi, et al. "Minimal rankings of the Cartesian product Kₙ ☐ Kₘ." Discussiones Mathematicae Graph Theory 32.4 (2012): 725-735. <http://eudml.org/doc/270880>.

@article{GilbertEyabi2012,

abstract = {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.},

author = {Gilbert Eyabi, Jobby Jacob, Renu C. Laskar, Darren A. Narayan, Dan Pillone},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph colorings; rankings of graphs; minimal rankings; rank number; arank number; Cartesian product of graphs; rook's graph},

language = {eng},

number = {4},

pages = {725-735},

title = {Minimal rankings of the Cartesian product Kₙ ☐ Kₘ},

url = {http://eudml.org/doc/270880},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Gilbert Eyabi

AU - Jobby Jacob

AU - Renu C. Laskar

AU - Darren A. Narayan

AU - Dan Pillone

TI - Minimal rankings of the Cartesian product Kₙ ☐ Kₘ

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 4

SP - 725

EP - 735

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

LA - eng

KW - graph colorings; rankings of graphs; minimal rankings; rank number; arank number; Cartesian product of graphs; rook's graph

UR - http://eudml.org/doc/270880

ER -

## References

top- [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. Zbl0801.68129
- [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. Zbl0515.65022
- [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 Zbl0863.05071
- [5] J. Ghoshal, R. Laskar and D. Pillone, Further results on minimal rankings, Ars Combin. 52 (1999) 181-198. Zbl0977.05048
- [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. Zbl0661.68063
- [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. Zbl1101.05040
- [9] R. Laskar and D. Pillone, Theoretical and complexity results for minimal rankings, J. Combin. Inform. System Sci. 25) (2000) 17-33. Zbl1219.05188
- [10] R. Laskar and D. Pillone, Extremal results in rankings, Congr. Numer. 149 (2001) 33-54. Zbl0989.05058
- [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. Zbl0697.65013
- [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. Zbl1286.05050
- [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. Zbl0764.68132
- [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.