On packing Hamilton cycles in \(\varepsilon\)-regular graphs
type: Item
instance of: scholarly article
title: On packing Hamilton cycles in \(\varepsilon\)-regular graphs
zbMATH Open document ID: 1061.05053
author: Michael Krivelevich
author: Alan Frieze
published in: Journal of Combinatorial Theory. Series B
publication date: 2005-05-04T00:00:00Z
review text: The main result of the paper says that if \(G\) is a graph on \(n\) vertices with the minimum degree \(\geq \alpha n,\) where \(\alpha \gg \varepsilon >10(\ln n/n)^{1/6},\) and for each disjoint subsets \(S,T\) of vertices of \( G,| S| ,| T| \geq \varepsilon n\) it is \(\left| \frac{e(S,T)}{| S| | T| } -\alpha\right | \leq \varepsilon ,\) then \(G\) contains \((\frac{\alpha }{2} -3\varepsilon )n\) edge-disjoint Hamilton cycles.
reviewed by: Peter Horák
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 2165073
zbMATH Keywords: Hamilton cycles
MaRDI profile type: Publication
full work available at URL: j.jctb.2004.12.003
OpenAlex ID: W2140606499
cites work: Problems and results in extremal combinatorics. I.
cites work: Q3720644
cites work: Q4044717
cites work: Q4745951
cites work: Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
cites work: On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs
cites work: Hamilton cycles in random subgraphs of pseudo-random graphs
cites work: The Game of JumbleG
cites work: Advances on the Hamiltonian problem -- a survey
cites work: Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
cites work: Q5477817
cites work: Hamiltonian games
cites work: A Hamiltonian game on \(K_{n,n}\)
cites work: Hamiltonian cycles in bipartite graphs
cites work: Decomposition of Finite Graphs into Open Chains
cites work: Q3768936
cites work: The Factorization of Linear Graphs
Wikidata QID: Q57401506
DOI: 10.1016/J.JCTB.2004.12.003
Recommended article: Counting and packing Hamilton \(\ell\)-cycles in dense hypergraphs
Recommended article: Packing tight Hamilton cycles in uniform hypergraphs
Recommended article: Packing Hamilton cycles in random and pseudo-random hypergraphs
Recommended article: Optimal Packings of Hamilton Cycles in Graphs of High Minimum Degree
Recommended article: Counting and packing Hamilton cycles in dense graphs and oriented graphs
Recommended article: Packing 1-plane Hamiltonian cycles in complete geometric graphs
Recommended article: Q5365090
Recommended article: Packing tight Hamilton cycles in 3-uniform hypergraphs
Recommended article: Packing and counting arbitrary Hamilton cycles in random digraphs
Recommended article: On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs
description: scientific article; zbMATH DE number 2165073