On a conjecture of Grünbaum on longest cycles (Q6080370): Difference between revisions

\textit{B. Grünbaum} [J. Comb. Theory, Ser. A 17, 31--38 (1974; Zbl 0259.05120)] conjectured that for any integer \(k \geq 2\), there exists no\(n\)-vertex graph \(G\) of circumference \(n-k\) in which the removal of any \(k\) vertices from \(G\) yields a Hamiltonian graph. The author shows that for any positive integers \(c\) and \(k\) there is an infinite family of \(c\)-connected graphs of circumference \(k\) less than their order, in which the limit (as the graphs' order tends to infinity) of the ratio between the number of \(k\)-vertex sets whose removal yields a Hamiltonian graph and the number of all \(k\)-vertex sets is 1. Motivated by a question, a relaxation of Grünbaum's conjecture, posed by \textit{D. Katona} et al. [Mat. Zametki 45, No. 1, 36--42 (1989; Zbl 0668.05044)], which states that whether an \(n\)-vertex graph in which every induced \(k\)-vertex subgraph is Hamiltonian must itself be Hamiltonian, where \(k\) is an integer satisfying \(n/2 < k < n-1\). In this paper, the conjecture is disproved for the case of \(k=n-2\). It is proven that there exists an infinite family of non-Hamiltonian graphs of increasing diameter \(d\) in which the removal of any two vertices at distance 1 or any distance at least \((d + 6)/2\) yields a Hamiltonian graph.