Discussiones Mathematicae Graph Theory 33(3) (2013) 603-611
doi: 10.7151/dmgt.1692

[BIBTex] [PDF] [PS]

Rainbow connection number of dense graphs

Xueliang Li, Mengmeng Liu

Center for Combinatorics and LPMC-TJKLC
Nankai University
Tianjin 300071, China

Ingo Schiermeyer

Institut für Diskrete Mathematik und Algebra
echnische Universität Bergakademie Freiberg
09596 Freiberg, Germany

Abstract

An edge-colored graph G is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper we show that rc(G) ≤ 3 if |E(G) | ≥ ((n −2) || 2)+2, and rc(G) ≤ 4 if |E(G) | ≥ ((n −3) || 2)+3. These bounds are sharp.

Keywords: edge-colored graph, rainbow coloring, rainbow connection number

2010 Mathematics Subject Classification: 05C15, 05C40.

References

[1]J.A. Bondy and U.S.R. Murty, Graph Theory ( GTM 244, Springer, 2008).
[2]G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85--98.
[3]A.B. Ericksen, A matter of security, Graduating Engineer & Computer Careers (2007) 24--28.
[4]A. Kemnitz and I. Schiermeyer, Graphs with rainbow connection number two, Disscuss. Math. Graph Theory 31 (2011) 313--320, doi: 10.7151/dmgt.1547.
[5]X. Li and Y. Sun, Rainbow Connections of Graphs (SpringerBriefs in Math., Springer, New York, 2012).

Received 8 November 2011
Revised 28 August 2012
Accepted 28 August 2012