On the threshold for rainbow connection number \(r\) in random graphs

详细信息    查看全文

• 作者：Annika Heckel ; Oliver Riordan
• 关键词：Random graph ; Rainbow connection number ; Sharp thresholds ; 05C80 ; 05C15
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：32
• 期：1
• 页码：161-174
• 全文大小：545 KB
• 参考文献：1.Bollobás, B.: The diameter of random graphs. Trans. Amer. Math. Soc. 267, 41–52 (1981)MATH MathSciNet CrossRef
  2.Caro, Y., Lev, A., Roditty, Y., Tuza, Z., Yuster, R.: On rainbow connection. Electron. J. Comb. 15, R57 (2008)MathSciNet
  3.Chartrand, G., Johns, G., McKeon, K., Zhang, P.: Rainbow connection in graphs. Math. Bohem. 133, 85–98 (2008)MATH MathSciNet
  4.Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23, 493–507 (1952)MATH MathSciNet CrossRef
  5.Dudek, A., Frieze, A., Tsourakakis, C.: Rainbow connection of random regular graphs. Preprint. Available at http://​arxiv.​org/​abs/​1311.​2299 (2013)
  6.Friedgut, E.: Sharp thresholds of graph properties, and the \(k\) -sat problem. J. Amer. Math. Soc. 12(4), 1017–1054 (1999)MATH MathSciNet CrossRef
  7.Frieze, A., Tsourakakis, C.: Rainbow connection of sparse random graphs. Electron. J. Comb. 19, P5 (2012)MathSciNet
  8.He, J., Liang, H.: On rainbow-\(k\) -connectivity of random graphs. Inf. Process. Lett. 112, 406–410 (2012)MATH MathSciNet CrossRef
  9.Heckel, A., Riordan, O.: The hitting time of rainbow connection number two. Electron. J. Combin. 19(4), P37 (2012)MathSciNet
  10.Janson, S., Łuczak, T., Ruciński, A.: Random graphs. Wiley, New York (2000)MATH CrossRef
  11.Li, X., Sun, Y.: Rainbow connections of graphs. Springer, New York (2012)MATH CrossRef
  
• 作者单位：Annika Heckel (1)
  Oliver Riordan (1)
  
  1. Mathematical Institute, University of Oxford, Radcliffe Observatory Quarter, Woodstock Road, Oxford, OX2 6GG, UK
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

We call an edge colouring of a graph \(G\) a rainbow colouring if every pair of vertices is joined by a rainbow path, i.e., a path where no two edges have the same colour. The minimum number of colours required for a rainbow colouring of the edges of \(G\) is called the rainbow connection number (or rainbow connectivity) \({\mathrm {rc}}(G)\) of \(G\). We investigate sharp thresholds in the Erdős–Rényi random graph for the property “\({\mathrm {rc}}(G)\le r\)” where \(r\) is a fixed integer. It is known that for \(r=2\), rainbow connection number \(2\) and diameter \(2\) happen essentially at the same time in random graphs. For \(r \ge 3\), we conjecture that this is not the case, propose an alternative threshold, and prove that this is an upper bound for the threshold for rainbow connection number \(r\). Keywords Random graph Rainbow connection number Sharp thresholds