DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 32(4) (2012) 725-735
DOI: https://doi.org/10.7151/dmgt.1634

Minimal Rankings of the Cartesian
Product Kn☐ Km

Gilbert Eyabi(1), Jobby Jacob(2), Renu C. Laskar(3)
Darren A. Narayan(2) and Dan Pillone(4)

(1) Anderson University, Anderson, SC 29621
(2) School of Mathematical Sciences, Rochester Institute of Technology Rochester, NY 14623
(3) Department of Mathematical Sciences, Clemson University Clemson SC 29634
(4) Bally Technologies, USA
e-mail: geyabi@andersonuniversity.edu
jxjsma@rit.edu
rclsk@clemson.edu
dansma@rit.edu
dpillone@hotmail.com

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 Kn ☐ Kn, and we investigate the arank number of Kn ☐ Km where n > m.

Keywords: graph colorings, rankings of graphs, minimal rankings, rank number, arank number, Cartesian product of graphs, rook's graph

2010 Mathematics Subject Classification: 05C78, 05C15, 05C76.

References

[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. 4th 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:1<45::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 P2n, 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 .

Received 20 June 2011
Revised 20 December 2011
Accepted 29 December 2011

Close