Name
Abstract | ||
|---|---|---|
We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large "bipartite hole" (two disjoint sets of vertices with no edges between them). This result extends Dirac's classical theorem, and is related to a theorem of Chvatal and Erdos. In detail, an (s, t)-bipartite-hole in a graph G consists of two disjoint sets of vertices S and T with vertical bar S vertical bar = s and vertical bar T vertical bar = t such that there are no edges between S and T; and (alpha) over tilde (G) is the maximum integer (R) such that G contains an (s, t)-bipartite-hole for every pair of nonnegative integers s and t with s + t = r. Our central theorem is that a graph G with at least three vertices is Hamiltonian if its minimum degree is at least (alpha) over tilde (G). From the proof we obtain a polynomial time algorithm that either finds a Hamilton cycle or a large bipartite hole. The theorem also yields a condition for the existence of k edge-disjoint Hamilton cycles. We see that for dense random graphs G(n, p), the probability of failing to contain many edge-disjoint Hamilton cycles is (1-p)(1+ o(1)) n. Finally, we discuss the complexity of calculating and approximating (alpha) over tilde (G). (C) 2017 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1002/jgt.22114 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
hamilton cycle,extremal graph theory,bipartite hole,random graphs | Integer,Discrete mathematics,Central limit theorem,Combinatorics,Disjoint sets,Random graph,Vertex (geometry),Hamiltonian (quantum mechanics),Hamiltonian path,Bipartite graph,Mathematics | Journal |
Volume | Issue | ISSN |
86.0 | 3.0 | 0364-9024 |
Citations | PageRank | References |
2 | 0.39 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin McDiarmid | 1 | 1071 | 167.05 |
| Nikola Yolov | 2 | 7 | 2.05 |