Geodesic
The Vertex-Rainbow Index of A Graph
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 669-681

Voir la notice de l'article provenant de la source Library of Science

The k-rainbow index rxk(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduce the concept of k-vertex-rainbow index rvxk(G) in this paper. In this paper, sharp upper and lower bounds of rvxk(G) are given for a connected graph G of order n, that is, 0 ≤ rvxk(G) ≤ n − 2. We obtain Nordhaus-Gaddum results for 3-vertex-rainbow index of a graph G of order n, and show that rvx3(G) + rvx3(Ḡ) = 4 for n = 4 and 2 ≤ rvx3(G) + rvx3(Ḡ) ≤ n − 1 for n ≥ 5. Let t(n, k, ℓ) denote the minimal size of a connected graph G of order n with rvxk(G) ≤ ℓ, where 2 ≤ ℓ ≤ n − 2 and 2 ≤ k ≤ n. Upper and lower bounds on t(n, k, ℓ) are also obtained.
Keywords: vertex-coloring, connectivity, vertex-rainbow S-tree, vertex- rainbow index, Nordhaus-Gaddum type 
@article{DMGT_2016_36_3_a11,
     author = {Mao, Yaping},
     title = {The {Vertex-Rainbow} {Index} of {A} {Graph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {669--681},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a11/}
}
TY  - JOUR
AU  - Mao, Yaping
TI  - The Vertex-Rainbow Index of A Graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 669
EP  - 681
VL  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a11/
LA  - en
ID  - DMGT_2016_36_3_a11
ER  - 
%0 Journal Article
%A Mao, Yaping
%T The Vertex-Rainbow Index of A Graph
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 669-681
%V 36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a11/
%G en
%F DMGT_2016_36_3_a11
Mao, Yaping. The Vertex-Rainbow Index of A Graph. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 669-681. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a11/