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


Cycle double covers and the semi-Kotzig frame
Authors:Dong Ye Cun-Quan Zhang
Affiliation:
  • Department of Mathematics, West Virginia University, Morgantown, WV 26506-6310, United States
  • Abstract:Let H be a cubic graph admitting a 3-edge-coloring c:E(H)→Z3 such that the edges colored with 0 and μ∈{1,2} induce a Hamilton circuit of H and the edges colored with 1 and 2 induce a 2-factor F. The graph H is semi-Kotzig if switching colors of edges in any even subgraph of F yields a new 3-edge-coloring of H having the same property as c. A spanning subgraph H of a cubic graph G is called a semi-Kotzig frame if the contracted graph G/H is even and every non-circuit component of H is a subdivision of a semi-Kotzig graph.In this paper, we show that a cubic graph G has a circuit double cover if it has a semi-Kotzig frame with at most one non-circuit component. Our result generalizes some results of Goddyn [L.A. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988], and Häggkvist and Markström [R. Häggkvist, K. Markström, Cycle double covers and spanning minors I, J. Combin. Theory Ser. B 96 (2006) 183-206].
    Keywords:
    本文献已被 ScienceDirect 等数据库收录!
    设为首页 | 免责声明 | 关于勤云 | 加入收藏

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