Geodesic
Arankings of Trees
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 415-437.

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 kranking for G if f(u) = f(v) implies that every u − v path contains a vertex w such that f(w) gt; f(u). A minimal k-ranking, f, of a graph, G, is a k-ranking with the property that decreasing the label of any vertex results in the ranking property being violated. The rank number χr(G) and the arank number ψr(G) are, respectively, the minimum and maximum value of k such that G has a minimal k-ranking. This paper establishes an upper bound for ψr of a tree and shows the bound is sharp for perfect k-ary trees.
Keywords: minimal ranking, coloring, tree 
@article{DMGT_2019_39_2_a8,
     author = {Pillone, D.},
     title = {Arankings of {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {415--437},
     publisher = {mathdoc},
     volume = {39},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a8/}
}
TY  - JOUR
AU  - Pillone, D.
TI  - Arankings of Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 415
EP  - 437
VL  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a8/
LA  - en
ID  - DMGT_2019_39_2_a8
ER  - 
%0 Journal Article
%A Pillone, D.
%T Arankings of Trees
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 415-437
%V 39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a8/
%G en
%F DMGT_2019_39_2_a8
Pillone, D. Arankings of Trees. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 415-437. http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a8/

[1] H. Alpert, Rank numbers of grid graphs, Discrete Math. 310 (2010) 3324–3333. doi:10.1016/j.disc.2010.07.022

[2] H.L. Bodlaender, J.R. Gilbert, H. Hafsteinsson and T. Kloks, Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, J. Algorithms 18 (1995) 238–255. doi:10.1006/jagm.1995.1009

[3] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Muller and Zs. Tuza, Rankings of graphs, SIAM J. Discrete Math. 11 (1998) 168–181. doi:10.1137/S0895480195282550

[4] G. Chartrand and P. Zhang, A First Course in Graph Theory (Dover Books, New York, 2012).

[5] P. de la Torre, R. Greenlaw and A.A. Schaeffer, Optimal ranking of trees in polynomial time, in: Proc. 4th ACM Symp. on Discrete Algorithms, V. Ramachandran (Ed(s)), (Austin, Texas, Society for Industrial and Applied Mathematics, 1993) 138–144.

[6] J.S. Deogun, T. Kloks, D. Kratsch and H. Muller, On vertex ranking for permutation and other graphs, in: Lecture Notes in Comput. Sci. 775, P. Enjalbert, E.W. Mayr and K.W. Wagner (Ed(s)), (Berlin, Springer-Verlag, 1994) 747–758. doi:10.1007/3-540-57785-8_187

[7] I.S. Duff and J.K. Reid, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software 9 (1983) 302–325. doi:10.1145/356044.356047

[8] D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965) 835–855. doi:10.2140/pjm.1965.15.835

[9] 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

[10] J. Ghoshal, R. Laskar and D. Pillone, Further results on minimal rankings, Ars Combin. 52 (1999) 191–198.

[11] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141–154. doi:10.1016/0012-365X(93)E0216-Q

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

[13] R. Laskar, D. Pillone, J. Jacob, G. Eyabi and D. Narayan, Minimal rankings of the Cartesian product Km □ Kn, Discuss. Math. Graph Theory 32 (2012) 725–735. doi:10.7151/dmgt.1634

[14] R. Laskar and D. Pillone, Theoretical and complexity results for minimal rankings, J. Comb. Inf. Syst. Sci. 25 (2000) 17–33.

[15] 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

[16] 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