Long cycles in graphs containing a 2-factor with many odd components (Q1343811): Difference between revisions

Let \(\sigma_ k(G)\) denote the minimum sum of the degrees of any \(k\) independent vertices of \(G\). It is shown that if \(G\) is a 2-connected graph of order \(n\) that contains a 2-factor with at least \(k\) odd components, and if \(\sigma_ 3(G)\geq n+ 2\), then \(G\) contains a cycle of length at least \(\min\{n, \sigma(G)/3+ n/2+ k/2\}\). There are several consequences of this theorem, one of which is a positive solution to a conjecture of Häggkvist that if \(G\) is a 2-connected graph of order \(n\) that has a 2-factor with at least \(k- 1\) odd components (actually \(2k\) components in the conjecture) and \(\sigma_ 2(G)\geq n- k\), then \(G\) is hamiltonian.