A difference set method for circulant decompositions of complete partite graphs into gregarious 4-cycles
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
The complete multipartite graph $K_{n(m)}$ with $n\geq 4$ partite sets of size $m$ is shown to have a decomposition into $4$-cycles in such a way that vertices of each cycle belong to distinct partite sets of $K_{n(m)}$, if 4 divides the number of edges. Such cycles are called {\it gregarious}, and were introduced by Billington and Hoffman (\cite{BH}) and redefined in \cite{BH2}. We independently came up with the result of \cite{BH2} by using a difference set method, and improved the result so that the composition is circulant, in the sense that it is invariant under the cyclic permutation of partite sets. The composition is then used to construct gregarious $4$-cycle decompositions when one partite set of the graph has different cardinality than that of others. Some results on joins of decomposable complete multipartite graphs are also presented.
Abstract
The complete multipartite graph $K_{n(m)}$ with $n\geq 4$ partite sets of size $m$ is shown to have a decomposition into $4$-cycles in such a way that vertices of each cycle belong to distinct partite sets of $K_{n(m)}$, if 4 divides the number of edges. Such cycles are called {\it gregarious}, and were introduced by Billington and Hoffman (\cite{BH}) and redefined in \cite{BH2}. We independently came up with the result of \cite{BH2} by using a difference set method, and improved the result so that the composition is circulant, in the sense that it is invariant under the cyclic permutation of partite sets. The composition is then used to construct gregarious $4$-cycle decompositions when one partite set of the graph has different cardinality than that of others. Some results on joins of decomposable complete multipartite graphs are also presented.
참고문헌 (11)
- B. Alspach, "Cycle decompositions of Kn and Kn", J. Combin. Theory Ser. B, 81, pp.77~99 (2001)
- E. Billington, "Decomposition of complete tripartite graphs into gre-garious 4-cycles", Discrete Math, 261, pp.87~111 (2003)
- E. Billington, "Equipartite and almost-equipartite gregarious 4-cycle decompositions", Discrete Math., 308(5), pp.696~714 (2008)
- E. Billington, "Resolvable gregarious cycle decompo-sitions of complete equipartite graphs", Discrete Math., 308(13), pp.2844~2853 (2008)
- N. J. Cavenagh, "Decompositions of complete multipartite graphs into cycles of even length", Graphs and Combinatorics, 16, pp.49~65 (2000)
- G. Chartrand, "Graphs and digraphs, 4th Ed" (2005), Chapman & Hall
- J. Liu, "The equipartite Oberwolfach problem and Ct-factorizations of complete equipar-tite graphs", J. Combin. Designs, 9, pp.42~49 (2000)
- J. Liu, "A generalization of the Oberwolfach problem with uniform tables", J. Combin. Theory Ser. A, 101, pp.20~34 (2003)
- M. Sajna, "On decomposiing Kn I into cycles of a xed odd length", Descrete Math., 244, pp.435~444 (2002)
- M. Sajna, "Cycle decompositions III: complete graphs and xed length cycles", J. Combin. Designs, 10, pp.27~78 (2002)
- D. Sotteau, "Decomposition of into cycles (circuits) of length 2k", J. Combin. Theory Ser. B, 30, pp.75~81 (1981)