首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号