Decompositions of Circulant Graphs into Short Cycles (Circuits)

循環圖分解成小迴圈之研究

黃孟晨(Meng-Chen Huang) ； 李鴻志(Hung-Chih Lee) ； 林正忠(Jenq-Jong Lin) ； 姚美玉(Mei-Yu Yao)

《嶺東學報》 26期 (2009/12) Pp. 115-125

https://doi.org/10.29850/LTJ.200912.0006

摘要

本文得到循環圖C(下標 n)(k)分解成4迴圈與8迴圈，以及有向循環圖C(上標 * 下標 n)(k)分解成有向4迴圈與有向8迴圈之充分條件。當k=「n/2」-1時，則得到4迴圈分解及有向4迴圈分解之充分必要條件。

關鍵字

迴圈 ； 有向迴圈 ； 分解 ； 循環圖 ； 有向循環圖

並列摘要

In this paper, the problems of decomposing the circulant graph C(subscript n)(k) (resp. the circulant digraph C(superscript * subscript n)(k)) into 4- and 8-cycles (resp. 4-and 8-circuits) are investigated. We obtain some sufficient conditions of the decompositions, and give the necessary and sufficient conditions of the 4- cycle decomposition of C(subscript n)(「n/2」-1) and the 4-circuit decomposition of C(superscript * subscript n) (「n/2」-1).

並列關鍵字

cycle ； circuit ； decomposition ； circulant graph ； circulant digraph

參考文獻

Alspach, B.,Gavlas, H.(2001).Cycle decompositions of Kn and Kn- I.J. Comb. Theory, Ser. B.81,77-99.

Alspach, B.,Gavlas, H.,Šajna, M.,Verrall, H.(2003).Cycle decompositions IV: complete directed graphs and ¯xed length directed cycles.J. Comb. Theory Ser. A.103,165-208.

Dean, M.(2006).On Hamilton cycle decomposition of 6-regular circulant graphs.Graphs Combin.22,331-340.

Dean, M.(2007).Hamilton cycle decomposition of 6-regular circulants of odd order.J. Comb. Des..15,91-97.

Hoffman, D. G.,Lindner, C. C.,Rodger, C. A.(1989).On the construction of odd cycle system.J. Graph Theory.13,417-426.