Pattern colored Hamilton cycles in random graphs. (English) Zbl 1407.05210
Summary: We consider the existence of patterned Hamilton cycles in randomly colored random graphs. Given a string \(\Pi\) over a set of colors \(\{1,2,\dots,r\}\), we say that a Hamilton cycle is \(\Pi\)-colored if the pattern repeats at intervals of length \(| \Pi|\) as we go around the cycle. We prove a hitting time result for the existence of such a cycle. We also prove a hitting time result for the related notion of \(\Pi\)-connected.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C12 | Distance in graphs |
References:
| [1] | M. Anastos and J. Briggs, Packing Directed and Hamilton Cycles Online, · Zbl 1391.05224 |
| [2] | D. Bal and A. M. Frieze, {\it Rainbow matchings and Hamilton cycles in random graphs}, Random Structures Algorithms, 48 (2016), pp. 503-523. · Zbl 1338.05209 |
| [3] | B. Bollobás, {\it The evolution of sparse graphs}, in Graph Theory and Combinatorics Proceedings, Cambridge Combinatorial Conference in Honour of Paul Erdös, 1984, B. Bollobás, ed., pp. 335-357. |
| [4] | C. Cooper and A. M. Frieze, {\it Multi-coloured Hamilton cycles in randomly coloured random graphs}, Combin. Probab. Comput., 11 (2002), pp. 129-134. · Zbl 1002.05019 |
| [5] | C. Cooper and A. M. Frieze, {\it Multicoloured Hamilton cycles in random graphs: An anti-Ramsey threshold}, Electron. J. Combin., 2 (1995), R19. · Zbl 0827.05055 |
| [6] | A. Dudek, S. English, and A. M. Frieze, {\it On rainbow Hamilton cycles in random hypergraphs}, Electronic J. Combin., 25 (2018). · Zbl 1391.05228 |
| [7] | L. Espig, A. M. Frieze, and M. Krivelevich, {\it Elegantly colored paths and cycles in edge colored random graphs}, SIAM J. Discrete Math., 32 (2018), pp. 1585-1618. · Zbl 1391.05229 |
| [8] | A. Ferber and M. Krivelevich, {\it Rainbow Hamilton cycles in random graphs and hypergraphs}, in Recent Trends in Combinatorics, IMA Vol. Math. Appl. 159, A. Beveridge, J. R. Griggs, L. Hogben, G. Musiker, and P. Tetali, eds., Springer, New York, 2016, pp. 167-189. · Zbl 1355.05225 |
| [9] | A. M. Frieze, {\it An algorithm for finding Hamilton cycles in random directed graphs}, J. Algorithms, 9 (1988), pp. 181-204. · Zbl 0646.68086 |
| [10] | A. M. Frieze and P. Loh, {\it Rainbow Hamilton cycles in random graphs}, Random Structures Algorithms, 44 (2014), pp. 328-354. · Zbl 1290.05097 |
| [11] | A. M. Frieze and B. McKay, {\it Multicoloured trees in random graphs}, Random Structures Algorithms, 5 (1994), pp. 45-56. · Zbl 0796.05084 |
| [12] | A. Frieze and M. Karoński, {\it Introduction to Random Graphs}, Cambridge University Press, Cambridge, UK, 2015. · Zbl 1328.05002 |
| [13] | A. M. Frieze and C. Tsourakakis, {\it Rainbow Connectivity of sparse random graphs}, Electron. J. Combin., 19 (2012). · Zbl 1372.05200 |
| [14] | A. Dudek, A. M. Frieze, and C. Tsourakakis, {\it Rainbow connection of random regular graphs}, SIAM J. Discrete Math., 29 (2015), pp. 2255-2266. · Zbl 1325.05148 |
| [15] | J. He and H. Liang, {\it On rainbow-\(k\)-connectivity of random graphs}, Inform. Process. Lett., 112 (2012), pp. 406-410. · Zbl 1243.05218 |
| [16] | A. Heckel and O. Riordan, {\it The hitting time of rainbow connection number two}, Electron. J. Combin., 19 (2012). · Zbl 1266.05034 |
| [17] | N. Kamcev̌, M. Krivelevich, and B. Sudakov, {\it Some remarks on rainbow connectivity}, J. Graph Theory, 83 (2016), pp. 372-383. · Zbl 1350.05078 |
| [18] | X. Li, Y. Shi, and Y. Sun, {\it Rainbow connections of graphs: A survey}, Graphs Combin., 29 (2013), pp. 1-38. · Zbl 1258.05058 |
| [19] | M. Molloy, {\it A Note on the Rainbow Connection of Random Regular Graphs}, Electron. J. Combin. 24, (2017). · Zbl 1369.05185 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
