Rainbow Connection in 3-Connected Graphs

被引：0
作者：
Xueliang Li
Yongtang Shi
机构：
[1] Nankai University,Center for Combinatorics and LPMC
来源：
Graphs and Combinatorics | 2013年 / 29卷
关键词：
Rainbow connection; Connectivity; The fan lemma; 05C15; 05C40;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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 by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper, we proved that rc(G) ≤ 3(n + 1)/5 for all 3-connected graphs.
引用
收藏
页码：1471 / 1475
页数：4
相关论文
共 15 条
  • [1] Caro Y.(2008)On rainbow connection Electron J. Combin. 15 R57-347
  • [2] Lev A.(2011)Hardness and algorithms for rainbow connectivity J. Comb. Optim 21 330-98
  • [3] Roditty Y.(2008)Rainbow connection in graphs Math. Bohemica 1 85-191
  • [4] Tuza Z.(2010)The rainbow connection of a graph is (at most) reciprocal to its minimum degree J. Graph Theory 63 185-undefined
  • [5] Yuster R.(undefined)undefined undefined undefined undefined-undefined
  • [6] Chakraborty S.(undefined)undefined undefined undefined undefined-undefined
  • [7] Fischer E.(undefined)undefined undefined undefined undefined-undefined
  • [8] Matsliah A.(undefined)undefined undefined undefined undefined-undefined
  • [9] Yuster R.(undefined)undefined undefined undefined undefined-undefined
  • [10] Chartrand G.(undefined)undefined undefined undefined undefined-undefined
12