Hamiltonicity of \(k\)-traceable graphs (Q540049)

Summary: 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\) \(\leq 10\), we determine the exact value of \(H(k)\). For \(k\) \(\geq 11\), we show that \(k + 2 \leq H(k) \leq {1\over 2} (3k - 5)\).