✦ LIBER ✦

The prism-free planar graphs and their cycles bases

✍ Scribed by David Hartvigsen; Russell Mardon

Publisher: John Wiley and Sons
Year: 1991
Tongue: English
Weight: 501 KB
Volume: 15
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190150408

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Dirac (1962) showed that the planar graphs with no prism minor are the graphs obtainable by 2‐sums from bonds, cycles, wheels and K~5~_e_'s. We give a new characterization of these graphs in terms of an optimization problem defined on the cycle bases of a graph.

📜 SIMILAR VOLUMES

On hamiltonian cycles in the prism over

On hamiltonian cycles in the prism over the odd graphs

✍ Letícia R. Bueno; Peter Horák 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 2 views

The Kneser graph K (n, k) has as its vertex set all k-subsets of an n-set and two k-subsets are adjacent if they are disjoint. The odd graph O k is a special case of Kneser graph when n = 2k +1. A long standing conjecture claims that O k is hamiltonian for all k>2. We show that the prism over O k is

Planar sections of the quadric of Lie cy

Planar sections of the quadric of Lie cycles and their Euclidean interpretations

✍ Jay P. Fillmore; Arthur Springer 📂 Article 📅 1995 🏛 Springer 🌐 English ⚖ 935 KB

Solution of problems of kotzig and Grünb

Solution of problems of kotzig and Grünbaum concerning the isolation of cycles in planar graphs

✍ O. V. Borodin 📂 Article 📅 1989 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 225 KB

Some properties of cycle-free directed g

Some properties of cycle-free directed graphs and the identification of the longest path

✍ Y.C. Chen; O. Wing 📂 Article 📅 1966 🏛 Elsevier Science 🌐 English ⚖ 444 KB

XBSTRACT: A number of interesting properties of a cycle-free directed graph are presented By making use of these properties an e.Oicient algorithm is deduced which identifies the longest path, or the Hamiltonian path if any, between every pair of vertices. The properties are expressed in terms of th

Connected cutsets of a graph and triangl

Connected cutsets of a graph and triangle bases of the cycle space

✍ P Duchet; M Las Vergnas; H Meyniel 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 602 KB

We investigate some properties of graphs whose cycle space has a basis constituted of triangles ('null-homotopic' graphs). We obtain characterizations in the case of planar graphs, and more generally, of graphs not contractible onto Ks. These characterizations involve separating subsets and decompos

On the max-cut problem for a planar, cub

On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation

✍ Carsten Thomassen 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

## Abstract Every 3‐connected planar, cubic, triangle‐free graph with __n__ vertices has a bipartite subgraph with at least 29__n__/24 − 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Example