On packing Hamilton cycles in \(\varepsilon\)-regular graphs (Q1775898)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On packing Hamilton cycles in \(\varepsilon\)-regular graphs
scientific article

    Statements

    On packing Hamilton cycles in \(\varepsilon\)-regular graphs (English)
    0 references
    0 references
    0 references
    4 May 2005
    0 references
    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.
    0 references
    0 references
    Hamilton cycles
    0 references
    0 references
    0 references