arXiv Analytics

Sign in

arXiv:2007.14502 [math.CO]AbstractReferencesReviewsResources

A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs

Viresh Patel, Fabian Stroh

Published 2020-07-28Version 1

We give a polynomial-time algorithm for detecting very long cycles in dense regular graphs. Specifically, we show that, given $\alpha \in (0,1)$, there exists a $c=c(\alpha)$ such that the following holds: there is a polynomial-time algorithm that, given a $D$-regular graph $G$ on $n$ vertices with $D\geq \alpha n$, determines whether $G$ contains a cycle on at least $n - c$ vertices. The problem becomes NP-complete if we drop either the density or the regularity condition. The algorithm combines tools from extremal graph theory and spectral partitioning as well as some further algorithmic ingredients.

Related articles: Most relevant | Search more
arXiv:1409.3325 [math.CO] (Published 2014-09-11)
Solution to a problem on hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions
arXiv:1407.4845 [math.CO] (Published 2014-07-17)
Hamiltonicity and $σ$-hypergraphs
arXiv:1201.5707 [math.CO] (Published 2012-01-27, updated 2013-11-13)
Hamiltonicity of 3-arc graphs