✦ LIBER ✦

On paths in planar graphs

✍ Scribed by Sanders, Daniel P.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 93 KB
Volume: 24
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199704)24:4<341::aid-jgt6>3.0.co;2-o

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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 👁 1 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

Induced paths in 5-connected graphs

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB 👁 1 views

We show that between any two vertices of a 5-connected graph there exists an induced path whose vertices can be removed such that the remaining graph is 2-connected.

On packing 3-vertex paths in a graph

✍ Atsushi Kaneko; Alexander Kelmans; Tsuyoshi Nishimura 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB

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

On the linear arboricity of planar graph

On the linear arboricity of planar graphs

✍ Wu, Jian-Liang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 2 views

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo, and Harary conjectured for any simple graph G with maximum degree ∆. The conjecture has been proved to be true for graphs having ∆ =

Some results on graphs without long indu

Some results on graphs without long induced paths

✍ Dong, Jinquan 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB

Let I(t) be the set of integers with the property that in every Pt-free connected graph G, the i-center C,(G) induces a connected subgraph. What is the minimum element of /(t)? In this paper, we prove that this minimum is [2t/3] -1 if t = 0 or Z(mod3) and is [ 2 t / 3 ] otherwise. Furthermore, as co