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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $k \geq 3$ be an integer, $h_{k}(G)$ be the number of vertices of degreeat least $2k$ in a graph $G$, and $\ell_{k}(G)$ be the number of vertices ofdegree at most $2k-2$ in $G$. Dirac and Erd\H{o}s proved in 1963 that if$h_{k}(G) - \ell_{k}(G) \geq k^{2} + 2k - 4$, then $G$ contains $k$vertex-disjoint cycles. For each $k\geq 2$, they also showed an infinitesequence of graphs $G_k(n)$ with $h_{k}(G_k(n)) - \ell_{k}(G_k(n)) = 2k-1$ suchthat $G_k(n)$ does not have $k$ disjoint cycles. Recently, the authors provedthat, for $k \geq 2$, a bound of $3k$ is sufficient to guarantee the existenceof $k$ disjoint cycles and presented for every $k$ a graph $G_0(k)$ with$h_{k}(G_0(k)) - \ell_{k}(G_0(k))=3k-1$ and no $k$ disjoint cycles. The goal ofthis paper is to refine and sharpen this result: We show that theDirac-Erd\H{o}s construction is optimal in the sense that for every $k \geq 2$,there are only finitely many graphs $G$ with $h_{k}(G) - \ell_{k}(G) \geq 2k$but no $k$ disjoint cycles. In particular, every graph $G$ with $|V(G)| \geq19k$ and $h_{k}(G) - \ell_{k}(G) \geq 2k$ contains $k$ disjoint cycles.

A sharp Dirac-Erd\H{o}s type bound for large graphs