|
|||||
|
|
Supereulerian graphs and the Petersen graph |
|
| Authors: | Xiao Min Li Lan Lei Hong-Jian Lai Meng Zhang |
| Institution: | 1. Department of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing, 400067, P. R. China 2. Department of Mathematics, West Virginia University, Morgantown, WV, 26506-6310, USA 3. College of Mathematics and System Sciences, Xinjiang University, Urumqi, 830046, P. R. China |
| Abstract: | A graph G is supereulerian if G has a spanning eulerian subgraph. Boesch et al. J. Graph Theory, 1, 79–84 (1977)] proposed the problem of characterizing supereulerian graphs. In this paper, we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph. This extends a former result of Catlin and Lai J. Combin. Theory, Ser. B, 66, 123–139 (1996)]. |
| Keywords: | Supereulerian graphs petersen graph edge-cut reduction contraction |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ | |