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

The classical Dirac theorem asserts that every graph $G$ on $n$ vertices withminimum degree $\delta(G) \ge \lceil n/2 \rceil$ is Hamiltonian. The lowerbound of $\lceil n/2 \rceil$ on the minimum degree of a graph is tight. In thispaper, we extend the classical Dirac theorem to the case where $\delta(G) \ge\lfloor n/2 \rfloor $ by identifying the only non-Hamiltonian graph families inthis case. We first present a short and simple proof. We then provide analternative proof that is constructive and self-contained. Consequently, weprovide a polynomial-time algorithm that constructs a Hamiltonian cycle, ifexists, of a graph $G$ with $\delta(G) \ge \lfloor n/2 \rfloor$, or determinesthat the graph is non-Hamiltonian. Finally, we present a self-contained prooffor our algorithm which provides insight into the structure of Hamiltoniancycles when $\delta(G) \ge \lfloor n/2 \rfloor$ and is promising for extendingthe results of this paper to the cases with smaller degree bounds.

A Simple Extension of Dirac's Theorem on Hamiltonicity