TOUGHNESS AND LONGEST CYCLES IN 2-CONNECTED PLANAR GRAPHS

Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let omega(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltoni an) if G is 4-connected. Recently, Jackson and Wormald showed that c(G ) greater than or equal to beta n(alpha) for some positive constants b eta and alpha approximate to 0.2 if G is 3-connected. Now let G have c onnectivity 2. Then c(G) may be as small as 4, as with K-2,K-n-2, unle ss we bound omega(G - S) for every subset S of V(G) with \S\ = 2. Defi ne xi(G) as the maximum of omega(G - S) taken over all 2-element subse ts S subset of or equal to V(G). We give an asymptotically sharp lower bound for the toughness of G in terms of S(G), and we show that c(G) greater than or equal to theta ln n for some positive constant theta d epending only on xi(G). In the proof we use a recent result of Gao and Yu improving Jackson and Wormald's result. Examples show that the low er bound on c(G) is essentially best-possible. (C) 1996 John Wiley & S ons, Inc.