# 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].
##### MSC:
 05C35 Extremal problems in graph theory 05C38 Paths and cycles
##### Keywords:
longest cycle; 3-connected graph