Hamiltonicity of $k$-Traceable Graphs

Frank Bullock, Peter Dankelmann, Marietjie Frick, Michael A. Henning, Ortrud R. Oellermann, Susan van Aardt


Let $G$ be a graph. A Hamilton path in $G$ is a path containing every vertex of $G$. The graph $G$ is traceable if it contains a Hamilton path, while $G$ is $k$-traceable if every induced subgraph of $G$ of order $k$ is traceable. In this paper, we study hamiltonicity of $k$-traceable graphs. For $k \geq 2$ an integer, we define $H(k)$ to be the largest integer such that there exists a $k$-traceable graph of order $H(k)$ that is nonhamiltonian. For $k \le 10$, we determine the exact value of $H(k)$. For $k \ge 11$, we show that $k+2 \le H(k) \le \frac{1}{2}(3k-5)$.

Full Text: