PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2012 | 32 | 4 | 725-735
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
725-735
Opis fizyczny
Daty
wydano
2012
otrzymano
2011-06-20
poprawiono
2011-12-20
zaakceptowano
2011-12-29
Twórcy
autor
• Anderson University, Anderson, SC 29621, USA
autor
• School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY 14623, USA
autor
• Department of Mathematical Sciences, Clemson University, Clemson SC 29634, USA
autor
• School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY 14623, USA
autor
• Bally Technologies, USA
Bibliografia
• [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: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 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.
Typ dokumentu
Bibliografia
Identyfikatory