The \((k,\ell )\) -Rainbow Index of Random Graphs

详细信息    查看全文

• 作者：Qingqiong Cai ; Xueliang Li ; Jiangli Song
• 关键词：Rainbow index ; Random graphs ; Threshold function
• 刊名：Bulletin of the Malaysian Mathematical Sciences Society
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：39
• 期：2
• 页码：765-771
• 全文大小：408 KB
• 参考文献：1.Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, New York (2004)
  2.Bollobás, B.: Random Graphs. Cambridge University Press, Cambridge (2001)CrossRef MATH
  3.Bondy, J.A., Murty, U.S.R.: Graph Theory, GTM 244. Springer, New York (2008)CrossRef MATH
  4.Cai, Q., Li, X., Song, J.: Solutions to conjectures on the \((k,\ell )\) -rainbow index of complete graphs. Networks 62, 220–224 (2013)MathSciNet
  5.Caro, Y., Lev, A., Roditty, Y., Tuza, Z., Yuster, R.: On rainbow connection. Electron. J. Combin. 15(1), R57 (2008)MathSciNet MATH
  6.Chandran, L., Das, A., Rajendraprasad, D., Varma, N.: Rainbow connection number and connected dominating sets. J. Graph Theory 71(2), 206–218 (2012)MathSciNet CrossRef MATH
  7.Chartrand, G., Johns, G., McKeon, K., Zhang, P.: Rainbow connection in graphs. Math. Bohem. 133, 85–98 (2008)MathSciNet MATH
  8.Chartrand, G., Johns, G., McKeon, K., Zhang, P.: The rainbow connectivity of a graph. Networks 54(2), 75–81 (2009)MathSciNet CrossRef MATH
  9.Chartrand, G., Okamoto, F., Zhang, P.: Rainbow trees in graphs and generalized connectivity. Networks 55, 360–367 (2010)MathSciNet MATH
  10.Fujita, S., Liu, H., Magnant, C.: Rainbow k-connection in dense graphs. Electron. Notes Discrete Math. 38, 361-366 (2011), or, J. Combin. Math. Combin. Comput., to appear
  11.Huang, X., Li, X., Shi, Y.: Note on the hardness of rainbow connections for planar and line graphs. Bull. Malays. Math. Sci. Soc. 38(3), 1235–1241 (2015)
  12.Krivelevich, M., Yuster, R.: The rainbow connection of a graph is (at most) reciprocal to its minimum degree. J. Graph Theory 63(3), 185–191 (2010)MathSciNet MATH
  13.Li, X., Sun, Y.: Rainbow Connections of Graphs. Springer Briefs in Math., Springer, New York (2012)CrossRef MATH
  14.Li, X., Sun, Y.: On the strong rainbow connection of a graph. Bull. Malays. Math. Sci. Soc. (2) 36(2), 299–311 (2013)MathSciNet MATH
  15.Li, S., Li, W., Li, X.: The generalized connectivity of complete bipartite graphs. Ars Combin. 104, 65–79 (2012)MathSciNet MATH
  16.Li, X., Shi, Y., Sun, Y.: Rainbow connections of graphs: a survey. Graphs Combin. 29(1), 1–38 (2013)MathSciNet CrossRef MATH
  17.Li, S., Li, W., Li, X.: The generalized connectivity of complete equipartition 3-partite graphs. Bull. Malays. Math. Sci. Soc. (2) 37(1), 103–121 (2014)MathSciNet MATH
  18.Li, H., Li, X., Mao, Y.: On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices. Bull. Malays. Math. Sci. Soc. (2), in press
  
• 作者单位：Qingqiong Cai (1)
  Xueliang Li (1)
  Jiangli Song (1)
  
  1. Center for Combinatorics and LPMC, Nankai University, Tianjin, 300071, China
  
• 刊物类别：Mathematics, general; Applications of Mathematics;
• 刊物主题：Mathematics, general; Applications of Mathematics;
• 出版者：Springer Singapore
• ISSN：2180-4206

文摘

A tree in an edge-colored graph G is said to be a rainbow tree if no two edges on the tree share the same color. Given two positive integers k, \(\ell \) with \(k\ge 3\), the \((k,\ell )\) -rainbow index \(rx_{k,\ell }(G)\) of G is the minimum number of colors needed in an edge-coloring of G such that for any set S of k vertices of G, there exist \(\ell \) internally disjoint rainbow trees connecting S. This concept was introduced by Chartrand et. al., and there have been very few known results about it. In this paper, we establish a sharp threshold function for \(rx_{k,\ell }(G_{n,p})\le k\) and \(rx_{k,\ell }(G_{n,M})\le k,\) respectively, where \(G_{n,p}\) and \(G_{n,M}\) are the usually defined random graphs.