Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk

✍ Scribed by Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M.

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 175 KB
• Volume: 34
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(200005)34:1<42::aid-jgt5>3.0.co;2-h

✦ Synopsis

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for k ≥ 3, there is a constant C k such that if 2m ≥ C k n then A k occurs in G n,m,k