✦ LIBER ✦

Spanning even subgraphs of 3-edge-connected graphs

✍ Scribed by Bill Jackson; Kiyoshi Yoshimoto

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 344 KB
Volume: 62
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20386

No coin nor oath required. For personal study only.

✦ Synopsis

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‐connectivity, we can find a spanning even subgraph in which every component has at least five vertices. We show that this is in some sense best possible by constructing an infinite family of 3‐edge‐connected graphs in which every spanning even subgraph has a 5‐cycle as a component. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 37–47, 2009

📜 SIMILAR VOLUMES

Connected Spanning Subgraphs of 3-Connec

Connected Spanning Subgraphs of 3-Connected Planar Graphs

✍ Hikoe Enomoto; Tadashi Iida; Katsuhiro Ota 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 339 KB

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.

Eulerian subgraphs in 3-edge-connected g

Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphs

✍ Zhi-Hong Chen; Hong-Jian Lai; Xiangwen Li; Deying Li; Jinzhong Mao 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 111 KB

## Abstract In this paper, we show that if __G__ is a 3‐edge‐connected graph with $S \subseteq V(G)$ and $|S| \le 12$, then either __G__ has an Eulerian subgraph __H__ such that $S \subseteq V(H)$, or __G__ can be contracted to the Petersen graph in such a way that the preimage of each vertex of th

Contractible Subgraphs in 3-Connected Gr

Contractible Subgraphs in 3-Connected Graphs

✍ Matthias Kriesell 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 154 KB

A subgraph H of a 3-connected finite graph G is called contractible if H is connected and G&V(H) is 2-connected. This work is concerned with a conjecture of McCuaig and Ota which states that for any given k there exists an f (k) such that any 3-connected graph on at least f (k) vertices possesses a

Long Cycles and 3-Connected Spanning Sub

Long Cycles and 3-Connected Spanning Subgraphs of Bounded Degree in 3-Connected K1, d-Free Graphs

✍ B. Jackson; N.C. Wormald 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 238 KB

Let $G$ be a 3-connected $K_{1, d}$-free graph on $n$ vertices. We show that $G$ contains a 3-connected spanning subgraph of maximum degree at most $2 d-1$. Using an earlier result of ours, we deduce that $G$ contains a cycle of length at least $\frac{1}{2} n^{c}$ where \(c=\left(\log

The spanning subgraphs of eulerian graph

The spanning subgraphs of eulerian graphs

✍ F. T. Boesch; C. Suffel; R. Tindell 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB

## Abstract It is shown that a connected graph __G__ spans an eulerian graph if and only if __G__ is not spanned by an odd complete bigraph __K__(2~m~ + 1, 2__n__ + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd