Decompositions of Circulant Graphs into Short Cycles (Circuits)

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

10.29850/LTJ.200912.0006

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

迴圈 ； 有向迴圈 ； 分解 ； 循環圖 ； 有向循環圖 ； cycle ； circuit ； decomposition ； circulant graph ； circulant digraph

嶺東學報

26期（2009 / 12 / 01）

115 - 125

英文

本文得到循環圖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).

1. Alspach, B.,Gavlas, H.(2001).Cycle decompositions of Kn and Kn- I.J. Comb. Theory, Ser. B,81,77-99.
2. 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.
3. Dean, M.(2007).Hamilton cycle decomposition of 6-regular circulants of odd order.J. Comb. Des.,15,91-97.
4. Dean, M.(2006).On Hamilton cycle decomposition of 6-regular circulant graphs.Graphs Combin,22,331-340.
5. Hoffman, D. G.,Lindner, C. C.,Rodger, C. A.(1989).On the construction of odd cycle system.J. Graph Theory,13,417-426.
6. Hsu, S.-L.(2008).Taiwan,Institute of Applied Information Technology, Ling Tung University.
7. Lee, H.-C.,Lin, C.(2005).Balanced star decompositions of regular multigraphs and λ-fold complete bipartite graphs.Discrete Math.,301,195-206.
8. Šajna, M.(2002).Cycle decompositions III: complete graphs and fixed length cycles.J. Comb. Des.,10,27-78.
9. Sotteau, D.(1981).Decomposition of Km,n (K* m,n) into Cycles (Circuits) of Length 2k.J. Comb. Theory Ser. B,30,75-81.