The 3-rainbow index and connected dominating sets

详细信息    查看全文

• 作者：Qingqiong Cai ; Xueliang Li ; Yan Zhao
• 关键词：3 ; rainbow index ; Connected dominating sets ; Rainbow paths
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：31
• 期：3
• 页码：1142-1159
• 全文大小：560 KB
• 参考文献：Bondy J, Murty USR (2008) Graph theory, vol 244. GTMSpringer, Berlin
  Cai Q, Li X, Song J (2013) Solutions to conjectures on the \((k,\ell )\) -rainbow index of complete graphs. Networks 62:220–224MathSciNet
  Cai Q, Li X, Song J (accepted-a) The \((k,\ell )\) -rainbow index of random graphs. Bull Malays Math Sci Soc
  Cai Q, Li X, Song J (accepted-b) The \((k,\ell )\) -rainbow index for complete bipartite and multipartite graphs. Bull Malays Math Sci Soc
  Caro Y, Lev A, Roditty Y, Tuza Z, Yuster R (2008) On rainbow connection. Electron J Combin 15(1):R57MathSciNet MATH
  Caro Y, West DB, Yuster R (2000) Connected domination and spanning trees with many leaves. SIAM J Discrete Math 13(2):202–211MathSciNet CrossRef MATH
  Chakraborty S, Fischer E, Matsliah A, Yuster R (2011) Hardness and algorithms for rainbow connection. J Combin Optim 21(3):330–347MathSciNet CrossRef MATH
  Chandran L, Das A, Rajendraprasad D, Varma N (2012) Rainbow connection number and connected dominating sets. J. Graph Theory 71(2):206–218MathSciNet CrossRef MATH
  Chartrand G, Johns G, McKeon K, Zhang P (2008) Rainbow connection in graphs. Math Bohem 133:85–98MathSciNet MATH
  Chartrand G, Johns G, McKeon K, Zhang P (2009) The rainbow connectivity of a graph. Networks 54(2):75–81
  Chartrand G, Okamoto F, Zhang P (2010) Rainbow trees in graphs and generalized connectivity. Networks 55:360–367MathSciNet MATH
  Chen L, Li X, Yang K, Zhao Y (in press) The 3-rainbow index of a graph. Discuss Math Graph Theory
  Griggs JR, Wu M (1992) Spanning trees in graphs of minimum degree 4 or 5. Discret Math 104(2):167–183
  Kleitman DJ, West DB (1991) Spanning trees with many leaves. SIAM J Discret Math 4(1):99–106
  Li X, Schiermeyer I, Yang K, Zhao Y (accepted) Graphs with 3-rainbow index \( n-1\) and \( n-2\) . Discuss Math Graph Theory
  Li X, Shi Y, Sun Y (2013) Rainbow connections of graphs: a survey. Graphs Combin 29:1–38
  Li X, Sun Y (2012) Rainbow connections of graphs., SpringerBriefs in MathSpringer, New YorkCrossRef MATH
  Liu T, Hu Y (2013) Some upper bounds for 3-rainbow index of graphs, arXiv preprint arXiv:​1310.​2355
  
• 作者单位：Qingqiong Cai (1)
  Xueliang Li (1)
  Yan Zhao (1)
  
  1. Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin, 300071, China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

A tree in an edge-colored graph is said to be rainbow if no two edges on the tree share the same color. An edge-coloring of \(G\) is called a 3-rainbow coloring if for any three vertices in \(G\), there exists a rainbow tree connecting them. The 3-rainbow index \(rx_3(G)\) of \(G\) is defined as the minimum number of colors that are needed in a 3-rainbow coloring of \(G\). This concept, introduced by Chartrand et al., can be viewed as a generalization of the rainbow connection. In this paper, we study the 3-rainbow index by using connected 3-way dominating sets and 3-dominating sets. We show that for every connected graph \(G\) on \(n\) vertices with minimum degree at least \(\delta \, (3\le \delta \le 5)\), \(rx_{3}(G)\le \frac{3n}{\delta +1}+4\), and the bound is tight up to an additive constant; whereas for every connected graph \(G\) on \(n\) vertices with minimum degree at least \(\delta \, (\delta \ge 3)\), we get that \(rx_{3}(G)\le \frac{\ln (\delta +1)}{\delta +1}(1+o_{\delta }(1))n+5\). In addition, we obtain some tight upper bounds of the 3-rainbow index for some special graph classes, including threshold graphs, chain graphs and interval graphs.