Even subgraphs of bridgeless graphs and 2-factors of line graphs |
| |
Authors: | Bill Jackson Kiyoshi Yoshimoto |
| |
Institution: | a School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, UK b Department of Mathematics, College of Science and Technology, Nihon University, Tokyo 101-8308, Japan |
| |
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. |
| |
Keywords: | Even subgraph Bridgeless graph 2-factor Line graph Claw-free graph |
本文献已被 ScienceDirect 等数据库收录! |
|