Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonian cycles, and to related questions. The corresponding decision problem, that asks whether a given graph is Hamiltonian (i. e. admits a Hamiltonian cycle), is one of Karp's famous NP-complete problems. It remains NP-complete on planar cubic graphs. In this paper we study graphs of bounded degree that are far from being Hamiltonian, where a graph G on n vertices is far from being Hamiltonian, if modifying a constant fraction of n edges is necessary to make G Hamiltonian. We exhibit classes of graphs of bounded degree that are locally Hamiltonian, i. e.  every subgraph induced by the neighbourhood of a small vertex set appears in some Hamiltonian graph , but that are far from being Hamiltonian. We then use these classes to obtain a lower bound in property testing. We show that in the bounded-degree graphmodel, Hamiltonicity is not testable with one-sided error probability and query complexity o(n) . This contrasts the known fact that on planar (or minor-free) graph classes, Hamiltonicity is testable with constant query complexity in the bounded-degree graph model with two-sided error . Our proof is an intricate construction that shows how to turn a d-regular graph into a graph that is far from being Hamiltonian, and we use d-regular expander graphs to maintain local Hamiltonicity .
Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonian cycles, and to related questions. The corresponding decision problem, that asks whether a given graph is Hamiltonian (i. \,e.\ admits a Hamiltonian cycle), is one of Karp's famous NP-complete problems. In this paper we study graphs of bounded degree that are far from being Hamiltonian, where a graph G on n vertices is far from being Hamiltonian, if modifying a constant fraction of n edges is necessary to make G Hamiltonian. We give an explicit deterministic construction of a class of graphs of bounded degree that are locally Hamiltonian, but (globally) far from being Hamiltonian. Here,locally Hamiltonian means that every subgraph induced by the neighbourhood of a small vertex set appears in some Hamiltonian graph . More precisely, we obtain graphs which differ in \Theta(n) edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected in the neighbourhood of o(n) vertices. Our class of graphs yields a class of hard instances for one-sided error property testers with linear query complexity. 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 deterministic constructions of hard instances for property testing are known. We believe that our construction may lead to future insights in graph theory and towards a characterisation of the properties hat are testable in the bounded-degree model .
R
e.
\,e.\
D
It remains NP-complete on planar cubic graphs.
R
far
far
R
far
far
R
exhibit classes of
give an explicit deterministic construction of a class of
R
i. e.
but (globally) far from being Hamiltonian. Here,
A
locally Hamiltonian
A
means that
R
, but that are far from being Hamiltonian. We then use these classes to obtain a lower bound in property testing. We show that in the bounded-degree graphmodel, Hamiltonicity is not testable with one-sided error probability and query complexity
. More precisely, we obtain graphs which differ in \Theta(n) edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected in the neighbourhood of
R
. This contrasts the known fact that on planar (or minor-free) graph classes, Hamiltonicity is testable with constant query complexity in the bounded-degree graph model with
vertices. Our class of graphs yields a class of hard instances for one-sided error property testers with linear query complexity. It is known that any property tester (even with
R
. Our proof is an intricate construction that shows how to turn a d-regular graph into a graph that is far from being Hamiltonian, and we use d-regular expander graphs to maintain local Hamiltonicity
) 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 deterministic constructions of hard instances for property testing are known. We believe that our construction may lead to future insights in graph theory and towards a characterisation of the properties hat are testable in the bounded-degree model