An explicit construction of graphs of bounded degree that are far from being Hamiltonian

Hamiltonian cycles in graphs were first studied in the 1850s. Since then, animpressive amount of research has been dedicated to identifying classes ofgraphs that allow Hamiltonian cycles, and to related questions. Thecorresponding decision problem, that asks whether a given graph is Hamiltonian(i.\,e.\ admits a Hamiltonian cycle), is one of Karp's famous NP-completeproblems. In this paper we study graphs of bounded degree that are \emph{far}from being Hamiltonian, where a graph $G$ on $n$ vertices is \emph{far} frombeing Hamiltonian, if modifying a constant fraction of $n$ edges is necessaryto make $G$ Hamiltonian. We give an explicit deterministic construction of aclass of graphs of bounded degree that are locally Hamiltonian, but (globally)far from being Hamiltonian. Here, \emph{locally Hamiltonian} means that everysubgraph induced by the neighbourhood of a small vertex set appears in someHamiltonian graph. More precisely, we obtain graphs which differ in $\Theta(n)$edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected inthe neighbourhood of $o(n)$ vertices. Our class of graphs yields a class ofhard instances for one-sided error property testers with linear querycomplexity. It is known that any property tester (even with two-sided error)requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010).This is proved via a randomised construction of hard instances. In contrast,our construction is deterministic. So far only very few deterministicconstructions of hard instances for property testing are known. We believe thatour construction may lead to future insights in graph theory and towards acharacterisation of the properties that are testable in the bounded-degreemodel.Comment: 19 pages, 4 figure