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

A Hamiltonian path (a Hamiltonian cycle) in a graph is a path (a cycle,respectively) that traverses all of its vertices. The problems of decidingtheir existence in an input graph are well-known to be NP-complete, in fact,they belong to the first problems shown to be computationally hard when thetheory of NP-completeness was being developed. A lot of research has beendevoted to the complexity of Hamiltonian path and Hamiltonian cycle problemsfor special graph classes, yet only a handful of positive results are known.The complexities of both of these problems have been open even for $4K_1$-freegraphs, i.e., graphs of independence number at most $3$. We answer thisquestion in the general setting of graphs of bounded independence number.  We also consider a newly introduced problem called\emph{Hamiltonian-$\ell$-Linkage} which is related to the notions of a pathcover and of a linkage in a graph. This problem asks if given $\ell$ pairs ofvertices in an input graph can be connected by disjoint paths that altogethertraverse all vertices of the graph. For $\ell=1$, Hamiltonian-1-Linkage asksfor existence of a Hamiltonian path connecting a given pair of vertices. Ourmain result reads that for every pair of integers $k$ and $\ell$, theHamiltonian-$\ell$-Linkage problem is polynomial time solvable for graphs ofindependence number not exceeding $k$. We further complement this generalpolynomial time algorithm by a structural description of obstacles toHamiltonicity in graphs of independence number at most $k$ for small values of$k$.

Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number