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} components. This upper bound is best possible. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1016/j.disc.2006.11.023 | Discrete Mathematics |
Keywords | Field | DocType |
even subgraph,2-factor,bridgeless graph,claw-free graph,line graph,claw free graph,factor h,upper bound | Discrete mathematics,Combinatorics,Minimum degree spanning tree,Multigraph,Line graph,Vertex (geometry),Claw-free graph,Upper and lower bounds,Nowhere-zero flow,Petersen graph,Mathematics | Journal |
Volume | Issue | ISSN |
307 | 22 | Discrete Mathematics |
Citations | PageRank | References |
12 | 0.95 | 9 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bill Jackson | 1 | 529 | 55.68 |
Kiyoshi Yoshimoto | 2 | 133 | 22.65 |