A note on decomposition of complete equipartite graphs into gregarious $6$-cycles
Bull. Korean Math. Soc. 2007 Vol. 44, No. 4, 709-719
Published online December 1, 2007
Jung Rae Cho
Pusan National University
Abstract : In \cite{CG}, it is shown that the complete multipartite graph $K_{n(2t)}$ having $n$ partite sets of size $2t$, where $n\geq6$ and $t\geq 1$, has a decomposition into {\it gregarious} $6$-cycles if $n \equiv 0,1,3$ or $4 \pmod{6}$. Here, a cycle is called {\it gregarious} if it has at most one vertex from any particular partite set. In this paper, when $n\equiv 0$ or $3 \pmod 6$, another method using difference set is presented. Furthermore, when $n\equiv 0\pmod{6}$, the decomposition obtained in this paper is {\it $\infty$-circular}, in the sense that it is invariant under the mapping which keeps the partite set which is indexed by $\infty$ fixed and permutes the remaining partite sets cyclically.
Keywords : multipartite graph, graph decomposition, gregarious cycle, difference set
MSC numbers : 05C70, 05B10
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd