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/