𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Toughness and longest cycles in 2-connected planar graphs

✍ Scribed by B�hme, T.; Broersma, H. J.; Veldman, H. J.

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
390 KB
Volume
23
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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) 2 ona for some positive constants , B and cy M 0.2 if G is 3-connected. Now let G have connectivity 2. Then c(G) may be as small as 4, as with K2,n-21 unless we bound w(G -S) for every subset S of V(G) with IS1 = 2. Define t(G) as the maximum of w(G -S) taken over all 2-element subsets S C V(G). We give an asymptotically sharp lower bound for the toughness of G in terms of J(G), and we show that c(G) 2 81nn for some positive constant 8 depending only on E(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.

📜 SIMILAR VOLUMES

Longest cycles in tough graphs
Longest cycles in tough graphs
✍ Jung, H.A.; Wittmann, P. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 347 KB 👁 1 views

In this article, we establish bounds for the length of a longest cycle C in a 2-connected graph G in terms of the minimum degree δ and the toughness t. It is shown that C is a Hamiltonian cycle or |C| ≥ (t + 1)δ + t.

Intersections of longest cycles in grid
Intersections of longest cycles in grid graphs
✍ Menke, B.; Zamfirescu, T.; Zamfirescu, C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 1 views

It is well-known that the largest cycles of a graph may have empty intersection. This is the case, for example, for any hypohamiltonian graph. In the literature, several important classes of graphs have been shown to contain examples with the above property. This paper investigates a (nontrivial) cl

On certain Hamiltonian cycles in planar
On certain Hamiltonian cycles in planar graphs
✍ B�hme, T.; Harant, J.; Tk�?, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 2 views

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that mus

Connected subgraphs with small degree su
Connected subgraphs with small degree sums in 3-connected planar graphs
✍ Enomoto, Hikoe; Ota, Katsuhiro 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh

Closure, 2-factors, and cycle coverings
Closure, 2-factors, and cycle coverings in claw-free graphs
✍ Ryj�?ek, Zden?k; Saito, Akira; Schelp, R. H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 239 KB 👁 1 views

In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217-224). For a claw-free graph G and its closure cl(G), we prove: ( 1 (2) G