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


Contractions of graphs with no spanning eulerian subgraphs
Authors:P. A. Catlin
Affiliation:(1) Wayne State University, 48202 Detroit, Michigan, USA
Abstract:LetpgE2 be a fixed integer, and letG be a connected graph onn vertices. Ifdelta(G)gE2, ifd(u)+d(v)>2n/p–2 holds wheneveruvnotinE(G), and ifn is sufficiently large compared top, then eitherG has a spanning eulerian subgraph, orG is contractible to a graphG1 of order less thenp and with no spanning eulerian subgraph. The casep=2 was proved by Lesniak-Foster and Williamson. The casep=5 was conjectured by Benhocine, Clark, Köhler, and Veldman, when they proved virtually the casep=3. The inequality is best-possible.
Keywords:05 C 45
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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