Hostname: page-component-7b7567c8c-tnzcf Total loading time: 0 Render date: 2026-11-13T21:52:40.534Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal Packings of Hamilton Cycles in Graphs of High Minimum Degree

Published online by Cambridge University Press:  20 December 2012

DANIELA KÜHN,
JOHN LAPINSKAS and
DERYK OSTHUS
DANIELA KÜHN
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK (e-mail: d.kuhn@bham.ac.uk, jal129@bham.ac.uk, d.osthus@bham.ac.uk)
JOHN LAPINSKAS
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK (e-mail: d.kuhn@bham.ac.uk, jal129@bham.ac.uk, d.osthus@bham.ac.uk)
DERYK OSTHUS
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK (e-mail: d.kuhn@bham.ac.uk, jal129@bham.ac.uk, d.osthus@bham.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study the number of edge-disjoint Hamilton cycles one can guarantee in a sufficiently large graph G on n vertices with minimum degree δ=(1/2+α)n. For any constant α>0, we give an optimal answer in the following sense: let regeven(n,δ) denote the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n vertices with minimum degree δ. Then the number of edge-disjoint Hamilton cycles we find equals regeven(n,δ)/2. The value of regeven(n,δ) is known for infinitely many values of n and δ. We also extend our results to graphs G of minimum degree δ ≥ n/2, unless G is close to the extremal constructions for Dirac's theorem. Our proof relies on a recent and very general result of Kühn and Osthus on Hamilton decomposition of robustly expanding regular graphs.

Keywords

Primary 05C45Secondary 05C3505C70

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 3 , May 2013, pp. 394 - 416
Copyright
Copyright © Cambridge University Press 2012

References

[1]Christofides, D., Kühn, D. and Osthus, D. (2012) Edge-disjoint Hamilton cycles in graphs, J. Combin. Theory B 102 1035–1060.CrossRefGoogle Scholar
[2]Csaba, B., Kühn, D., Lo, A., Osthus, D. and Treglown, A. Personal communication.Google Scholar
[3]Dirac, G. A. (1952) Some theorems on abstract graphs. Proc. London Math. Soc. 2 69–81.Google Scholar
[4]Hartke, S. G., Martin, R. and Seacrest, T. Relating minimum degree and the existence of a k-factor. Research manuscript.Google Scholar
[5]Hartke, S. G. and Seacrest, T. Random partitions and edge-disjoint Hamiltonian cycles. Preprint.Google Scholar
[6]Hefetz, D., Kühn, D., Lapinskas, J. and Osthus, D. Optimal covers with Hamilton cycles in random graphs. Preprint.Google Scholar
[7]Jackson, B. (1979) Edge-disjoint Hamilton cycles in regular graphs of large degree. J. London Math. Soc. 19 13–16.CrossRefGoogle Scholar
[8]Katerinis, P. (1985) Minimum degree of a graph and the existence of k-factors. Proc. Indian Acad. Sci. Math. Sci. 94 123–127.Google Scholar
[9]Knox, F., Kühn, D. and Osthus, D. Edge-disjoint Hamilton cycles in random graphs. Preprint.Google Scholar
[10]Krivelevich, M. and Samotij, W. (2012) Optimal packings of Hamilton cycles in sparse random graphs. SIAM J. Discrete Math. 26 964–982.Google Scholar
[11]Kühn, D. and Osthus, D. Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments. Preprint.Google Scholar
[12]Kühn, D. and Osthus, D. Hamilton decompositions of regular expanders: applications. Preprint.Google Scholar
[13]Kühn, D., Osthus, D. and Treglown, A. (2010) Hamiltonian degree sequences in digraphs, J. Combin. Theory Ser. B 100 367–380.Google Scholar
[14]Nash-Williams, C. St. J. A. (1970) Hamiltonian lines in graphs whose vertices have sufficiently large valencies. In Combinatorial Theory and its Applications III: Proc. Colloq., Balatonfüred, 1969, North-Holland, pp. 813–819.Google Scholar
[15]Nash-Williams, C. St. J. A. (1971) Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency. In Studies in Pure Mathematics (Presented to Richard Rado), Academic Press, pp. 157–183.Google Scholar
[16]Nash-Williams, C. St. J. A. (1971) Hamiltonian arcs and circuits. In Recent Trends in Graph Theory: Proc. Conf., New York, 1970, Springer, pp. 197–210.Google Scholar
[17]Tutte, W. T. (1952) The factors of graphs. Canad. J. Math. 4 314–328.Google Scholar