Premium
Toughness and longest cycles in 2‐connected planar graphs
Author(s) -
Böhme T.,
Broersma H. J.,
Veldman H. J.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199611)23:3<257::aid-jgt5>3.0.co;2-r
Subject(s) - combinatorics , mathematics , planar graph , upper and lower bounds , graph , hamiltonian path , planar , constant (computer programming) , discrete mathematics , mathematical analysis , computer science , computer graphics (images) , programming language
Let G be a planar graph on n vertices, let c ( G ) denote the length of a longest cycle of G, and let w ( G ) denote the number of components of G. By a well‐known theorem of Tutte, c ( G ) = n (i.e., G is hamiltonian) if G is 4‐connected. Recently, Jackson and Wormald showed that c ( G ) ≥ β n α for some positive constants β and α ≅ 0.2 if G is 3‐connected. Now let G have connectivity 2. Then c ( G ) may be as small as 4, as with K 2, n ‐2 , unless we bound w ( G − S ) for every subset S of V ( G ) with | S | = 2. Define ξ( G ) as the maximum of w ( G − S ) taken over all 2‐element subsets S ⊆ V ( G ). We give an asymptotically sharp lower bound for the toughness of G in terms of ξ( G ), and we show that c ( G ) ≥ θ ln n for some positive constant θ depending only on ξ( G ). In the proof we use a recent result of Gao and Yu improving Jackson and Wormald's result. Examples show that the lower bound on c ( G ) is essentially best‐possible. © 1996 John Wiley & Sons, Inc.