Hamiltonian cycles in \(n\)-factor-critical graphs (Q5948969): Difference between revisions

A graph \(G\) is said to be \((k,n)\)-factor-critical if \(G-S\) has a \(k\)-factor for any \(S \subset V(G)\) with \(|S|=n\). In this paper it is proved that if \(G\) is a 2-connected \((1,n)\)-factor-critical graph of order \(p\) with \(\sigma_3(G)\geq \frac{3}{2}(p-n-1)\), then \(G\) is hamiltonian with some exceptions. The authors conjecture that if \(G\) is a 2-connected \((k,n)\)-factor-critical graph of order \(p\) with \(\sigma_3(G)\geq \frac{3}{2}(p-n-k)\), then \(G\) is hamiltonian with some exceptions. They characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, the conjecture for \(k\leq 2\) is verified. Here \(\sigma_3(G)\) denotes the minimum degree of vertices taken over all independent sets consisting of three vertices.