- Tytuł:
- On the Rainbow Vertex-Connection
- Autorzy:
-
Li, Xueliang
Shi, Yongtang - Powiązania:
- https://bibliotekanauki.pl/articles/30146636.pdf
- Data publikacji:
- 2013-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
rainbow vertex-connection
vertex coloring
minimum degree
2-step dominating set - Opis:
- 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 vertex-connected. It was proved that if $G$ is a graph of order $n$ with minimum degree $ \delta $, then $ rvc(G) < 11n//\delta$. In this paper, we show that $rvc(G) \le 3n//(δ+1)+5$ for $ \delta \ge \sqrt{n-1} -1 $ and $ n \le 290 $, while $ rvc(G) \le 4n//(δ + 1) + 5 $ for $ 16 \le \delta \le \sqrt{n-1}-2 $ and $ rvc(G) \le 4n//(\delta + 1) + C(\delta) $ for $6 \le \delta \le 15$, where $ C(\delta) = e^\frac{ 3 \log (\delta^3 + 2 \delta^2 +3)-3(\log 3 - 1)}{\delta - 3} - 2$. We also prove that $ rvc(G) \le 3n//4 − 2 $ for $ \delta = 3$, $ rvc(G) \le 3n//5 − 8//5$ for $\delta = 4$ and $rvc(G) \le n//2 − 2$ for $\delta = 5$. Moreover, an example constructed by Caro et al. shows that when $ \delta \ge \sqrt{n-1} - 1 $ and $ \delta = 3, 4, 5 $, our bounds are seen to be tight up to additive constants.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 307-313
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł