✦ LIBER ✦

On generating planar graphs

✍ Scribed by David Barnette

Publisher: Elsevier Science
Year: 1974
Tongue: English
Weight: 699 KB
Volume: 7
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(74)90035-1

No coin nor oath required. For personal study only.

✦ Synopsis

A 3-valent graph G 1s cyclically n-connected provided one must cut at least n edges in ori4r to separate any two circuits of 6. If G is cyclically n-connected but any separation of G by cutting n edges yields a component consisting of a simple circuit, then we say that G is ' strong& cyclicaZZy n-connected. We prove tht there exists a graph GO such that all strongly cyclically 4-connected planar graphs, other than the graph of the cube and the pentagonal prism, can be generated from Go by adding edges. We introduce two operations called adding a pai? af edges and replacing a face. We prove that using these two operations together with adding edges we can generate the cyclically S-connected planar graphs.

📜 SIMILAR VOLUMES

Generating 5-regular planar graphs

✍ Guoli Ding; Jinko Kanno; Jianning Su 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

## Abstract For __k__=0, 1, 2, 3, 4, 5, let ${\cal{P}}\_{k}$ be the class of __k__ ‐edge‐connected 5‐regular planar graphs. In this paper, graph operations are introduced that generate all graphs in each ${\cal{P}}\_{k}$. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 219–240, 2009

Generalizations of planar graphs

✍ Ranel E. Erickson 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 677 KB

On planar hypohamiltonian graphs

✍ Gábor Wiener; Makoto Araya 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for eve

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.

Antisymmetric flows on planar graphs

✍ T. H. Marshall 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

## Abstract We prove that every oriented planar graph admits a homomorphism to the Paley tournament __P__~271~ and hence that every oriented planar graph has an antisymmetric flow number and a strong oriented chromatic number of at most 271. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 200–210

A note on planar graphs

✍ David P. Brown; Alan Budner 📂 Article 📅 1965 🏛 Elsevier Science 🌐 English ⚖ 612 KB

Some new properties of the distribution of elements and vertices with respect to the windows of a connected planar graph G are established. It is also shown that a window matrix of G has properties similar to the properties of an incidence matrix of a graph which is not necessarily planar. A method