Spanning even subgraphs of 3‐edge‐connected graphs |
| |
| Authors: | Bill Jackson Kiyoshi Yoshimoto |
| |
| Institution: | 1. School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom;2. Department of Mathematics, College of Science and Technology, Nihon University, Tokyo 101‐8308, Japan |
| |
| 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 |
| |
| Keywords: | longest cycle dominating cycle edge degree remote edges triangle‐free graph bipartite graph |
|
|
