English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We present a tight extremal threshold for the existence of Hamilton cycles ingraphs with large minimum degree and without a large ``bipartite hole`` (twodisjoint sets of vertices with no edges between them). This result extendsDirac's classical theorem, and is related to a theorem of Chv\'atal andErd\H{o}s.  In detail, an $(s, t)$-bipartite-hole in a graph $G$ consists of two disjointsets of vertices $S$ and $T$ with $|S|= s$ and $|T|=t$ such that there are noedges between $S$ and $T$; and $\widetilde{\alpha}(G)$ is the maximum integer$r$ such that $G$ contains an $(s, t)$-bipartite-hole for every pair ofnon-negative integers $s$ and $t$ with $s + t = r$. Our central theorem is thata graph $G$ with at least $3$ vertices is Hamiltonian if its minimum degree isat least $\widetilde{\alpha}(G)$.  From the proof we obtain a polynomial time algorithm that either finds aHamilton cycle or a large bipartite hole. The theorem also yields a conditionfor the existence of $k$ edge-disjoint Hamilton cycles. We see that for denserandom graphs $G(n,p)$, the probability of failing to contain manyedge-disjoint Hamilton cycles is $(1 - p)^{(1 + o(1))n}$. Finally, we discussthe complexity of calculating and approximating $\widetilde{\alpha}(G)$.

Hamilton cycles, minimum degree and bipartite holes