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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.