Edge-disjoint hamilton cycles in random graphs

F. Knox; D. Kühn; D. Osthus

doi:10.1002/rsa.20510

Edge-disjoint hamilton cycles in random graphs

F. Knox, D. Kühn, D. Osthus

Mathematics

Research output: Contribution to journal › Article › peer-review

26 Citations (Scopus)

Abstract

We show that provided log50n/n≤p≤1-n-1/4log9n we can with high probability find a collection of ⌊δ(G)/2⌋ edge-disjoint Hamilton cycles in G~Gn,p, plus an additional edge-disjoint matching of size ⌊n/2⌋ if δ(G) is odd. This is clearly optimal and confirms, for the above range of p, a conjecture of Frieze and Krivelevich.

Original language	English
Pages (from-to)	397-445
Number of pages	49
Journal	Random Structures and Algorithms
Volume	46
Issue number	3
Early online date	2 Jul 2013
DOIs	https://doi.org/10.1002/rsa.20510
Publication status	Published - 1 May 2015

Keywords

Hamilton cycles
Packings
Random graphs

ASJC Scopus subject areas

Computer Graphics and Computer-Aided Design
Software
General Mathematics
Applied Mathematics

Access to Document

10.1002/rsa.20510

Edge-Colourings and Hamilton Decompostitions of Graphs
Osthus, D. & Kuhn, D.
Engineering & Physical Science Research Council
1/06/12 → 30/09/14
Project: Research Councils
Directed graphs and the regularity method
Kuhn, D. & Osthus, D.
Engineering & Physical Science Research Council
1/10/07 → 31/03/11
Project: Research Councils

Cite this

@article{764ca5ab4970434c8c5e6190955aae59,

title = "Edge-disjoint hamilton cycles in random graphs",

abstract = "We show that provided log50n/n≤p≤1-n-1/4log9n we can with high probability find a collection of ⌊δ(G)/2⌋ edge-disjoint Hamilton cycles in G~Gn,p, plus an additional edge-disjoint matching of size ⌊n/2⌋ if δ(G) is odd. This is clearly optimal and confirms, for the above range of p, a conjecture of Frieze and Krivelevich.",

keywords = "Hamilton cycles, Packings, Random graphs",

author = "F. Knox and D. K{\"u}hn and D. Osthus",

year = "2015",

month = may,

day = "1",

doi = "10.1002/rsa.20510",

language = "English",

volume = "46",

pages = "397--445",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "3",

}

TY - JOUR

T1 - Edge-disjoint hamilton cycles in random graphs

AU - Knox, F.

AU - Kühn, D.

AU - Osthus, D.

PY - 2015/5/1

Y1 - 2015/5/1

N2 - We show that provided log50n/n≤p≤1-n-1/4log9n we can with high probability find a collection of ⌊δ(G)/2⌋ edge-disjoint Hamilton cycles in G~Gn,p, plus an additional edge-disjoint matching of size ⌊n/2⌋ if δ(G) is odd. This is clearly optimal and confirms, for the above range of p, a conjecture of Frieze and Krivelevich.

AB - We show that provided log50n/n≤p≤1-n-1/4log9n we can with high probability find a collection of ⌊δ(G)/2⌋ edge-disjoint Hamilton cycles in G~Gn,p, plus an additional edge-disjoint matching of size ⌊n/2⌋ if δ(G) is odd. This is clearly optimal and confirms, for the above range of p, a conjecture of Frieze and Krivelevich.

KW - Hamilton cycles

KW - Packings

KW - Random graphs

UR - http://www.scopus.com/inward/record.url?scp=84924815534&partnerID=8YFLogxK

U2 - 10.1002/rsa.20510

DO - 10.1002/rsa.20510

M3 - Article

AN - SCOPUS:84924815534

SN - 1042-9832

VL - 46

SP - 397

EP - 445

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 3

ER -

Edge-disjoint hamilton cycles in random graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Projects

Edge-Colourings and Hamilton Decompostitions of Graphs

Directed graphs and the regularity method

Cite this