Premium
Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least k
Author(s) -
Bollobás B.,
Cooper C.,
Fenner T. I.,
Frieze A. M.
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(200005)34:1<42::aid-jgt5>3.0.co;2-h
Subject(s) - combinatorics , mathematics , disjoint sets , degree (music) , discrete mathematics , graph , enhanced data rates for gsm evolution , constant (computer programming) , simple graph , matching (statistics) , statistics , computer science , telecommunications , physics , acoustics , programming language
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 2 m ≥ C k n then A k occurs in G n,m,k with probability tending to 1 as n → ∞. © 2000 John Wiley & Sons, Inc. J. Graph Theory 34: 42–59, 2000