zbMATH — the first resource for mathematics

Spanning even subgraphs of 3-edge-connected graphs. (English) Zbl 1180.05057
Summary: By Petersen’s theorem, a bridgeless cubic graph has a 2-factor. H. Fleischner [“Spanning eulerian subgraphs, the splitting lemma, and Petersen’s theorem”, Discrete Math. 101, No.1-3, 33–37 (1992: Zbl 0764.05051)] 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.

05C38 Paths and cycles
05C40 Connectivity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI
[1] Chen, Reduction techniques for super-Eulerian graphs and related topics-a survey pp 53– (1995)
[2] Diestel, Graph Theory (2000)
[3] Fleischner, Spanning Eulerian subgraphs, the splitting lemma, and Petersen’s theorem, Discrete Math 101 pp 33– (1992) · Zbl 0764.05051
[4] Jackson, Even subgraphs of bridgeless graphs and 2-factors of line graphs, Discrete Math 307 pp 2775– (2007) · Zbl 1127.05080
[5] Jaeger, Flows and generalized coloring theorems in graphs, J Combin Theory Ser B 26 pp 205– (1979) · Zbl 0422.05028
[6] Kochol, Superposition and constructions of graphs without nowhere-zero k-flows, European J Combin 23 pp 281– (2002) · Zbl 1010.05062
[7] Máčajová, Constructing hypohamiltonian snarks with cyclic connectivity 5 and 6, Electron J Combin 14 pp R18– (2007)
[8] Mader, A reduction method for edge-connectivity in graphs, Ann Discrete Math 3 pp 145– (1978) · Zbl 0389.05042
[9] Petersen, Die Theorie der regulären Graphs, Acta Math 15 pp 193– (1891)
[10] Plesník, Connectivity of regular graphs and the existence of 1-factors, Mat Časopis Sloven Akad Vied 22 pp 310– (1972)
[11] Zhan, On hamiltonian line graphs and connectivity, Discrete Math 89 pp 89– (1991) · Zbl 0727.05037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.