zbMATH — the first resource for mathematics

On the longest cycles in a class of 3-connected graphs. (English) Zbl 0793.05080
Capobianco, Michael F. (ed.) et al., Graph theory and its applications: East and West. Proceedings of the first China-USA international conference, held in Jinan, China, June 9-20, 1986. New York: New York Academy of Sciences,. Ann. N. Y. Acad. Sci. 576, 107-117 (1989).
All graphs considered here are finite and simple. For a given graph \(G= (V(G),E(G))\), denote by \(n(G)\), \(\alpha(G)\), \(\delta(G)\), and \(c(G)\) its order, independence number, minimum degree, and the length of the longest cycle of \(G\), respectively. Let \[ f=\min\bigl\{d(u)+ d(v)\mid u,\;v\text{ are nonadjacent vertices of }G\bigr\}. \] In [Ann. Discrete Math. 3, 75-92 (1978; Zbl 0376.05035)], G. A. Dirac proved that, if \(G\) is a 2- connected graph on \(n\) vertices and \(f\geq 4\) is defined as previously, then \(c(G)\geq\min\{f,n\}\). In [J.-C. Bermond, Selected topics in graph theory, 127-157 (1978; Zbl 0429.05052)], it is stated that Bondy and Nash-Williams (1971) proved that if \(G\) is a 2-connected graph satisfying \(\delta(G)\geq\max\{\alpha(G)\mid (n+ 2)/3\}\), then \(G\) is Hamiltonian. The purpose of this paper is to prove the following theorem.
Main theorem: Let \(G\) be a 3-connected graph satisfying that \(\alpha(G)\leq \delta(G)\), \(n(G)= n\) and \(d(u)+ d(v)\geq f\) holds for any two nonadjacent vertices \(u\), \(v\) of \(G\); then \(c(G)\geq \min(3(f- 2)/2,n)\).
Notice that this result is best possible in view of the graph \(G=(r+1)K_ 2+ rK_ 1\), the joint graph of \((r+ 1)K_ 2\) and \(rK_ 1\), where \(r\) is an integer \(\geq 3\) and \(K_ i\) is an \(i\)-clique, since in this graph we have \(f= 2r+2\), \(c(G)=3r\), and \(3(f- 2)/2= 3r\).
For the entire collection see [Zbl 0788.00046].
05C35 Extremal problems in graph theory
05C38 Paths and cycles