Name
Abstract | ||
|---|---|---|
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 hamiltonian) 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 beta and alpha approximate to 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,K-n-2, unless we bound omega(G - S) for every subset S of V(G) with \S\ = 2. Define xi(G) as the maximum of omega(G - S) taken over all 2-element subsets 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 depending 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 lower bound on c(G) is essentially best-possible. (C) 1996 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1996 | 3.3.CO;2-Z" target="_self" class="small-link-text"10.1002/(SICI)1097-0118(199611)23:33.3.CO;2-Z | Journal of Graph Theory |
Keywords | Field | DocType |
planar graph,lower bound | Longest cycle,Combinatorics,Vertex (geometry),Bound graph,Hamiltonian (quantum mechanics),Upper and lower bounds,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
23 | 3 | 0364-9024 |
Citations | PageRank | References |
1 | 0.35 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Böhme | 1 | 3 | 1.42 |
| H. J. Broersma | 2 | 266 | 33.68 |
| H. J. Veldman | 3 | 262 | 44.44 |