# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## On the Rainbow Vertex-connection

 Xueliang Li and Yongtang Shi Center for Combinatorics and LPMC-TJKLC Nankai University, Tianjin 300071, China

## 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 vertex-connected. 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 δ ≥ √n −1 −1 and n ≥ 290, while rvc(G) ≤ 4n/( δ+1)+5 for 16 ≤ δ ≤ √n −1 −2 and rvc(G) ≤ 4n/( δ+1)+C( δ) for 6 ≤ δ ≤ 15, where C( δ) = e(3log( δ3+2 δ2+3) −3(log3 −1))/(δ −3) −2. 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 δ ≥ √n −1 −1 and δ = 3,4,5, our bounds are seen to be tight up to additive constants.

Keywords: rainbow vertex-connection, vertex coloring, minimum degree, 2-step dominating set

2010 Mathematics Subject Classification: 05C15, 05C40.

## References

  N. Alon and J.H. Spencer, The Probabilistic Method, 3rd ed. (Wiley, New York, 2008).  J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, 2008).  Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) R57.  S. Chakraborty, E. Fischer, A. Matsliah and R. Yuster, Hardness and algorithms for rainbow connectivity, J. Comb. Optim. 21 (2011) 330--347, doi: 10.1007/s10878-009-9250-9 .  L. Chandran, A. Das, D. Rajendraprasad and N. Varma, Rainbow connection number and connected dominating sets, J. Graph Theory 71 (2012) 206?-218, doi: 10.1002/jgt.20643.  G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohemica 133 (2008) 85--98.  L. Chen, X. Li and Y. Shi, The complexity of determining the rainbow vertex-connection of a graph, Theoret. Comput. Sci. 412(35) (2011) 4531--4535, doi: 10.1016/j.tcs.2011.04.032.  J.R. Griggs and M. Wu, Spanning trees in graphs with minimum degree 4 or 5, Discrete Math. 104 (1992) 167--183, doi: 10.1016/0012-365X(92)90331-9.  D.J. Kleitman and D.B. West, Spanning trees with many leaves, SIAM J. Discrete Math. 4 (1991) 99--106, doi: 10.1137/0404010.  M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185--191, doi: /10.1002/jgt.20418.  X. Li and Y. Sun, Rainbow Connections of Graphs (Springer Briefs in Math., Springer, New York, 2012).  N. Linial and D. Sturtevant, Unpublished result (1987).  I. Schiermeyer, Rainbow connection in graphs with minimum degree three, IWOCA 2009, LNCS 5874 (2009) 432--437.