DMGT

Discussiones Mathematicae Graph Theory 19(2) (1999) 219-227
DOI: https://doi.org/10.7151/dmgt.1096

NOTE ON CYCLIC DECOMPOSITIONS OF COMPLETE BIPARTITE GRAPHS INTO CUBES

Dalibor Froncek

Department of Applied Mathematics
Technical University Ostrava
17 listopadu, 708 33 Ostrava, Czech Republic
e-mail: dalibor.froncek@vsb.cz

Abstract

So far, the smallest complete bipartite graph which was known to have a cyclic decomposition into cubes Q_d of a given dimension d was K_{d2^d−1, d2^d−2}. We improve this result and show that also K_{d2^d−2,
d2^d−2} allows a cyclic decomposition into Q_d. We also present a cyclic factorization of K_8,8 into Q₄.

Keywords: hypercubes, bipartite graphs, factorization.

1991 Mathematics Subject Classification: 05C70.

References

[1]	S. El-Zanati and C. Vanden Eynden, Decompositions of K_m,n into cubes, J. Comb. Designs 4 (1) (1996) 51-57, doi: 10.1002/(SICI)1520-6610(1996)4:1<51::AID-JCD5>3.0.CO;2-Z.
[2]	A. Rosa, On certain valuations of the vertices of a graph, Internat. Sympos. ICC Rome, Dunod, Paris, 1967, 349-355.
[3]	C. Vanden Eynden, Decompositions of complete bipartite graphs, Ars Combinatoria, to appear.

Received 3 February 1999
Revised 30 October 1999