𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Pancyclicity of 3-connected graphs: Pairs of forbidden subgraphs

✍ Scribed by Ronald J. Gould; Tomasz Łuczak; Florian Pfender

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
232 KB
Volume
47
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We characterize all pairs of connected graphs {X, Y} such that each 3‐connected {X, Y}‐free graph is pancyclic. In particular, we show that if each of the graphs in such a pair {X, Y} has at least four vertices, then one of them is the claw K~1,3~, while the other is a subgraph of one of six specified graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 183–202, 2004

📜 SIMILAR VOLUMES

Pancyclic subgraphs of random graphs
Pancyclic subgraphs of random graphs
✍ Choongbum Lee; Wojciech Samotij 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract An __n__‐vertex graph is called pancyclic if it contains a cycle of length __t__ for all 3≤__t__≤__n__. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if __p__>__n__^−1/2^, then the random graph __G__(__n, p__) a.a.s. satisfies the f

Pancyclicity of connected circulant grap
Pancyclicity of connected circulant graphs
✍ Bogdanowicz, Z. R. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 299 KB 👁 1 views

The circulant G,(al,. . . , ak), where 0 < al < ... < a k < ( n + 1 ) / 2 , is defined as the vertex-transitive graph that has vertices ifal,. . . ,if a k (mod n) adjacent to each vertex i. In this work we show that the connected circulants of degree at least three contain all even cycles. In additi

2-Connected Spanning Subgraphs of Planar
2-Connected Spanning Subgraphs of Planar 3-Connected Graphs
✍ D.W. Barnette 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 278 KB

We prove that every planar 3-connected graph has a 2-connected spanning subgraph of maximum valence 15 . We give an example of a planar 3 -connected graph with no spanning 2-connected subgraph of maximum valence five. i) 1994 Academic Press, Inc.

Spanning even subgraphs of 3-edge-connec
Spanning even subgraphs of 3-edge-connected graphs
✍ Bill Jackson; Kiyoshi Yoshimoto 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB

## Abstract By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connec