𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On certain Hamiltonian cycles in planar graphs

✍ Scribed by B�hme, T.; Harant, J.; Tk�?, M.

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
162 KB
Volume
32
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 must be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show that every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cyles of length less than five contains at least 2 O(n 1/4 ) distinct Hamiltonian cycles.

📜 SIMILAR VOLUMES

More than one tough chordal planar graph
More than one tough chordal planar graphs are Hamiltonian
✍ B�hme, Thomas; Harant, Jochen; Tk�?, Michal 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB 👁 1 views

We prove the result stated in the title. Furthermore, it is proved that for any > 0, there is a 1-tough chordal planar graph G such that the length of a longest cycle of G is less than |V (G )|.

On paths in planar graphs
On paths in planar graphs
✍ Sanders, Daniel P. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 2 views

This paper generalizes a theorem of Thomassen on paths in planar graphs. As a corollary, it is shown that every 4-connected planar graph has a Hamilton path between any two specified vertices x, y and containing any specified edge other than xy.

Toughness and longest cycles in 2-connec
Toughness and longest cycles in 2-connected planar graphs
✍ B�hme, T.; Broersma, H. J.; Veldman, H. J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 390 KB 👁 1 views

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 positiv

On light edges and triangles in projecti
On light edges and triangles in projective planar graphs
✍ Sanders, Daniel P. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 376 KB 👁 1 views

An edge or face of an embedded graph is light if the sum of the degrees of the vertices incident with it is small. This paper parallelizes four inequalities on the number of light edges and light triangles from the plane to the projective plane. Each of the four inequalities is shown to be the best

Proof of a conjecture on cycles in a bip
Proof of a conjecture on cycles in a bipartite graph
✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 244 KB 👁 1 views

It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k ≥ 2, there exists . This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n ≥ 3k, i.e., M (k) ≤ 3k. W

Cycles in a graph whose lengths differ b
Cycles in a graph whose lengths differ by one or two
✍ Bondy, J. A.; Vince, A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 1 views

Several problems concerning the distribution of cycle lengths in a graph have been proposed by P. Erdös and colleagues. In this note two variations of the following such question are answered. In a simple graph where every vertex has degree at least three, must there exist two cycles whose lengths d