Article ID Journal Published Year Pages File Type
4650291 Discrete Mathematics 2007 11 Pages PDF
Abstract

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n   vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10}max{1,(3n-4)/10} components. This upper bound is best possible.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,