Decomposing Crowns into 4- and 8-cycles (Circuits)

皇冠圖之4迴圈及8迴圈分解

10.29850/LTJ.200912.0003

陳永仁(Yung-Jen Chen)；林正忠(Jenq-Jong Lin)；李鴻志(Hung-Chih Lee)；姚美玉(Mei-Yu Yao)

皇冠圖 ； 迴圈 ； 有向迴圈 ； 分解 ； crown ； cycle ； circuit ； decomposition

嶺東學報

26期（2009 / 12 / 01）

49 - 60

英文

本文探討皇冠圖C(下標 n, k)之4迴圈及8迴圈分解，及有向皇冠圖C(上標 * 下標 n, k)之4有向迴圈及8有向迴圈分解之問題，得到分解存在之充分條件。至於特殊有向皇冠圖C(上標 * 下標 n, n-1)方面，則得到分解存在之充分必要條件。

In this paper, we investigate the problems of decomposing the crown C(subscript n, k) (resp. directed crown C(superscript * subscript n, k)) into 4-cycles and 8-cycles (resp. 4-circuits and 8-circuits). Some sufficient conditions of the problems are given. Moreover, we obtain the necessary and sufficient conditions of 4-circuit decompositions and 8-circuit decompositions of C(superscript * subscript n, n-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 fixed length directed cycles.J. Comb. Theory Ser. A,103,165-208.
3. Hoffman, D. G.,Lindner, C. C.,Rodger, C. A.(1989).On the construction of odd cycle system.J. Graph Theory,13,417-426.
4. Hsu, S.-L.(2008).Taiwan,Institute of Applied Information Technology, Ling Tung University.
5. Lin, C.,Lin, J.-J.(2000).Cycle decompositions of crowns.Discrete Math,220,251-255.
6. Ma, J.,Pu, L.,Shen, H.(1994).Cycle decompositions of Kn,n- I.SIAM J. Discrete Math,20,603-609.
7. Šajna, M.(2002).Cycle decompositions III: complete graphs and fixed length cycles.J. Comb. Des.,10,27-78.
8. Sotteau, D.(1981).Decomposition of Km,n (K* m,n) into Cycles (Circuits) of Length 2k.J. Comb. Theory Ser. B,30,75-81.