论文标题
有界图的明确构造远非哈密顿
An explicit construction of graphs of bounded degree that are far from being Hamiltonian
论文作者
论文摘要
在1850年代首次研究了图形中的哈密顿周期。从那时起，大量的研究一直致力于识别允许哈密顿周期和相关问题的图形类别。询问给定图的相应决策问题是否是哈密顿（i。在本文中，我们研究了\ emph {far}的界图图，如果是$ n $ dertices上的图$ g $，则是\ emph {far}，如果修改$ n $ edges的恒定分数是使$ g $ g $ g $ hamiltonian所必需的。我们给出了一类有界程度的图表的明确确定性结构，这些图形是当地的哈密顿量，但（在全球范围内）远非是哈密顿人。在这里，\ emph {本地哈密顿}意味着由小顶点集邻里引起的每个子图出现在一些汉密尔顿图中。更确切地说，我们获得的图形在$θ（n）$边缘与任何哈密顿图的差异都不同，但是在$ O（n）$顶点的附近，无法检测到非汉密尔顿。我们的图表为具有线性查询复杂性的单面错误属性测试仪提供了一类硬实例。众所周知，任何属性测试仪（即使有双面误差）都需要线性数量的查询来测试汉密尔顿（Yoshida，ITO，2010年）。通过随机结构硬实例证明了这一点。相反，我们的构建是确定性的。到目前为止，仅知道对财产测试的硬实例的确定性结构很少。我们认为，我们的构建可能会导致图理论的未来见解，并朝着对界度模型中可检验的属性的表征。
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 \emph{far} from being Hamiltonian, where a graph $G$ on $n$ vertices is \emph{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, \emph{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 $Θ(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 that are testable in the bounded-degree model.
