Long cycles, degree sums and neighborhood unions (Q1309446): Difference between revisions

Let \(\sigma_ 3\) denote the minimum degree sum of any 3 pairwise nonadjacent vertices. Let \(\text{NC}_ k\) be the minimum number of vertices in a neighborhood union of any \(k\) pairwise nonadjacent vertices. The authors show that every 1-tough graph of order \(n \geq 3\) with \(\sigma_ 3 \geq n+r\) has a cycle of length at least \(\min \{n,n+\text{NC}_{r+5+\varepsilon (n+r)} (G)-\alpha(G)\}\), where \(\varepsilon (i)=0,2\), or 1, accordingly as \(i \equiv 0,1\) or \(2 \pmod 3\), respectively. They also prove that if \(G\) is a 1-tough graph of order \(n \geq 3\) with \(\sigma_ 3 \geq n+r\) and \(n\geq 8t-6r-17\) then \(G\) has a cycle of length at least \(\min \{n,2 \text{NC}_ t(G)\}\). Similar results hold for 2-connected graphs.