$Q_4$-Factorization of $\lambda K_n$ and $\lambda K_x(m)$

  • Oğuz Doğan Koç University


In this study, we show that necessary conditions for $Q_4$-factorization of $\lambda{K_n}$ and $\lambda{K_{x(m)}}$ (complete $x$ partite graph with parts of size $m$) are sufficient. We proved that there exists a $Q_4$-factorization of $\lambda{K_{x(m)}}$ if and only if $mx\equiv{0} \pmod{16}$ and $\lambda{m(x-1)}\equiv{0}\pmod{4}$. This result immediately gives that $\lambda K_n$ has a $Q_4$-factorization if and only if $n\equiv 0 \pmod{16}$ and $\lambda \equiv 0 \pmod{4}$.

Author Biography

Oğuz Doğan, Koç University



P. Adams, D. Bryant, and S. El-Zanati, -fold cube decompositions, Australas. J. Combin. 11 (1995), 197–210.

P. Adams, D. E. Bryant, and B. M. Maenhaut, Cube factorizations of complete graphs, J. Combin. Des. 12 (2004) 381–388.

D. E. Bryant, S. I. El-Zanati, B. M. Maenhaut, and C. Vanden Eynden, Decomposition of complete graphs into 5-cubes, J. Combin. Des. 14 (2006) 159–166.

C. J. Colbourn and J.H. Dinitz, The CRC Handbook of Combinatorial Designs, 2nd Edition, Chapman and Hall/CRC, Boca Raton, FL, 2006.

S. El-Zanati, M. Plantholt, and C. Vanden Eynden, Graph decompositions into generalized cubes, Ars Combin. 49 (1998), 237–247.

S. El-Zanati and C. Vanden Eynden, Factorizations of complete multipartite graphs into generalized cubes, J. Graph Theory 33 (2000), 144–150.

S. El-Zanati and C. Vanden Eynden, Decomposing complete graphs into cubes, Discuss. Math. Graph Theory 26 (2006), 141–147.

A. Kotzig, Selected open problems in graph theory, Graph Theory and Related Topics, Academic Press, New York, (1979), 258–267.

A. Kotzig, Decompositions of complete graphs into isomorphic cubes, J. Combin. Theory Ser. B 31 (1981) 292–296.

M. Maheo, Strongly graceful graphs, Discrete Math. 29 (1980), 39–46.

X. Sun and G. Ge Resolvable group divisible designs with block size four and general index, Discrete Math. 309 (2009), 2982–2989.

J. Wang, Cube factorizations of complete multipartite graphs, Ars Combin. 99 (2011), 243-256.