On the Rainbow Vertex-Connection

Xueliang Li, and Yongtang Shi. "On the Rainbow Vertex-Connection." Discussiones Mathematicae Graph Theory 33.2 (2013): 307-313. <http://eudml.org/doc/268108>.

@article{XueliangLi2013,
abstract = {A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ + 1) + 5 for [xxx] and rvc(G) ≤ 4n/(δ + 1) + C(δ) for 6 ≤ δ ≤ 15, where [xxx]. We also prove that rvc(G) ≤ 3n/4 − 2 for δ = 3, rvc(G) ≤ 3n/5 − 8/5 for δ = 4 and rvc(G) ≤ n/2 − 2 for δ = 5. Moreover, an example constructed by Caro et al. shows that when [xxx] and δ = 3, 4, 5, our bounds are seen to be tight up to additive constants.},
author = {Xueliang Li, Yongtang Shi},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {rainbow vertex-connection; vertex coloring; minimum degree; 2-step dominating set},
language = {eng},
number = {2},
pages = {307-313},
title = {On the Rainbow Vertex-Connection},
url = {http://eudml.org/doc/268108},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Xueliang Li
AU - Yongtang Shi
TI - On the Rainbow Vertex-Connection
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 2
SP - 307
EP - 313
AB - A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ + 1) + 5 for [xxx] and rvc(G) ≤ 4n/(δ + 1) + C(δ) for 6 ≤ δ ≤ 15, where [xxx]. We also prove that rvc(G) ≤ 3n/4 − 2 for δ = 3, rvc(G) ≤ 3n/5 − 8/5 for δ = 4 and rvc(G) ≤ n/2 − 2 for δ = 5. Moreover, an example constructed by Caro et al. shows that when [xxx] and δ = 3, 4, 5, our bounds are seen to be tight up to additive constants.
LA - eng
KW - rainbow vertex-connection; vertex coloring; minimum degree; 2-step dominating set
UR - http://eudml.org/doc/268108
ER -