Contractions of graphs with no spanning eulerian subgraphs |
| |
Authors: | P. A. Catlin |
| |
Affiliation: | (1) Wayne State University, 48202 Detroit, Michigan, USA |
| |
Abstract: | Letp2 be a fixed integer, and letG be a connected graph onn vertices. If(G)2, ifd(u)+d(v)>2n/p–2 holds wheneveruvE(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 等数据库收录! |
|