Long cycles in 1-tough graphs with large degree sums (Q687919)

Let \(c(G)\) denote the circumference of a graph \(G\). The following notations are used in the statements of results that are announced in this letter: \(\sigma_ 3(G)=\min\{\sum^ 3_{i=1} d(v_ i): \{v_ 1,v_ 2,v_ 3\}\) is an independent set in \(G\}\), \(\overline\sigma_ 3(G)=\min\{\sum^ 3_{i=1} d(v_ i)- |\bigcap^ 3_{i=1} N(v_ i)|: \{v_ 1,v_ 2,v_ 3\}\) is an independent set in \(G\}\), \(\rho_ 3(G)=\min\{|\bigcup^ 3_{i=1} N(v_ i)|: \{v_ 1,v_ 2,v_ 3\}\) is an independent set in \(G\}\), and \(\rho^*_ 3(G)=\min\{|\bigcup^ 3_{i=1} N(v_ i)|: \{v_ 1,v_ 2,v_ 3\}\) is an independent set in \(G\) with \(\bigcap^ 3_{i=1} N(v_ i)\neq\varnothing\}\). Results: Let \(G\) be a 1-tough graph of order \(n\). (a) If \(\sigma_ 3(G)\geq n\geq 3\), then \(c(G)\geq\min\{n,2\rho^*_ 3(G)+ 4\}\); consequently, \(c(G)\geq \min\{n,2\rho_ 3(G)+ 4\}\). (b) If \(\sigma_ 3(G)\geq (3n-13)/2\) for \(n\geq 15\) and odd, or \(\sigma_ 3(G)\geq (3n-16)/2\) for \(n\geq 16\) and even, or \(\sigma_ 3(G)\geq n\) where \(n\leq 14\), then \(G\) is Hamiltonian. (c) If \(\sigma_ 3(G)\geq n\geq 3\) and \(\rho^*_ 3(G)\geq (n-4)/2\), then \(G\) is Hamiltonian.