Long cycles in 1-tough graphs with large degree sums

MaRDI QIDQ687919zbMATH OpenFDO

Authors Jianping Li, Feng Tian, Lianzhu Zhang

Publication date 13 April 1994

Published in Chinese Science Bulletin (Search for Journal in Brave)

zbMATH Keywords

1-tough graphs circumference Hamiltonian graphs independent set long cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

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.

Recommendations

Cited in

(12)

This page was built for publication: Long cycles in 1-tough graphs with large degree sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q687919)