Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650291 | Discrete Mathematics | 2007 | 11 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Bill Jackson, Kiyoshi Yoshimoto,