Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656949 | Journal of Combinatorial Theory, Series B | 2013 | 25 Pages |
Abstract
In this paper we prove a similar result using methods that do not rely on the Regularity Lemma. In particular, we prove that every graph on n vertices with minimum degree δ⩾n/2+3n3/4ln(n) contains α(δ,n)/2â3n7/8(lnn)1/4/2 edge-disjoint Hamiltonian cycles. Our proof rests on a structural result that is of independent interest: let G be a graph on n vertices, where n=pq. Then there exists a partition of the vertices of G into q parts of size p such that every vertex v has at least deg(v)/qâmin{deg(v),p}â
ln(n) neighbors in each part.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Stephen G. Hartke, Tyler Seacrest,