Rainbow Connection Number of Dense Graphs

Xueliang Li; Mengmeng Liu; Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 3, page 603-611
  • ISSN: 2083-5892

Abstract

top
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)| ≥ [...] + 2, and rc(G) ≤ 4 if |E(G)| ≥ [...] + 3. These bounds are sharp.

How to cite

top

Xueliang Li, Mengmeng Liu, and Ingo Schiermeyer. "Rainbow Connection Number of Dense Graphs." Discussiones Mathematicae Graph Theory 33.3 (2013): 603-611. <http://eudml.org/doc/267532>.

@article{XueliangLi2013,
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)| ≥ [...] + 2, and rc(G) ≤ 4 if |E(G)| ≥ [...] + 3. These bounds are sharp.},
author = {Xueliang Li, Mengmeng Liu, Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge-colored graph; rainbow coloring; rainbow connection number},
language = {eng},
number = {3},
pages = {603-611},
title = {Rainbow Connection Number of Dense Graphs},
url = {http://eudml.org/doc/267532},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Xueliang Li
AU - Mengmeng Liu
AU - Ingo Schiermeyer
TI - Rainbow Connection Number of Dense Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 3
SP - 603
EP - 611
AB - 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)| ≥ [...] + 2, and rc(G) ≤ 4 if |E(G)| ≥ [...] + 3. These bounds are sharp.
LA - eng
KW - edge-colored graph; rainbow coloring; rainbow connection number
UR - http://eudml.org/doc/267532
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, 2008). 
  2. [2] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. Zbl1199.05106
  3. [3] A.B. Ericksen, A matter of security, Graduating Engineer & Computer Careers (2007) 24-28. 
  4. [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[Crossref] 
  5. [5] X. Li and Y. Sun, Rainbow Connections of Graphs (SpringerBriefs in Math., Springer, New York, 2012). doi:10.1007/978-1-4614-3119-0 [Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.