Splits of circuits

详细信息    查看全文

• 作者：Tommy R. Jensen
• 关键词：Graph circuit ; Cycle Double-Cover Conjecture ; Split ; Semiextension ; Planar graph ; Jordan Curve Theorem ; Hamilton circuit
• 刊名：Discrete Mathematics
• 出版年：2010
• 出版时间：6 November 2010
• 年：2010
• 卷：310
• 期：21
• 页码：3026-3029
• 全文大小：230 K

文摘

This paper discusses an attempt at identifying a property of circuits in (nonplanar) graphs resembling the separation property of circuits in planar graphs derived from the Jordan Curve Theorem.

If G is a graph and C is a circuit in G, we say that two circuits in G form a split of C if the symmetric difference of their edges sets is equal to the edge set of C, and if they are separated in G by the intersection of their vertex sets.

García Moreno and Jensen, A note on semiextensions of stable circuits, Discrete Math. 309 (2009) 4952–4954, asked whether such a split exists for any circuit C whenever G is 3-connected. We observe that if true, this implies a strong form of a version of the Cycle Double-Cover Conjecture suggested in the Ph.D. thesis of Luis Goddyn. The main result of the paper shows that the property holds for Hamilton circuits in cubic graphs.