ArticleOriginal scientific text

Title

Note on cyclic decompositions of complete bipartite graphs into cubes

Authors 1

Affiliations

  1. Department of Applied Mathematics, Technical University Ostrava, 17 listopadu, 708 33 Ostrava, Czech Republic

Abstract

So far, the smallest complete bipartite graph which was known to have a cyclic decomposition into cubes Qd of a given dimension d was Kd2d-1,d2d-2. We improve this result and show that also Kd2d-2,d2d-2 allows a cyclic decomposition into Qd. We also present a cyclic factorization of K8,8 into Q₄.

Keywords

hypercubes, bipartite graphs, factorization

Bibliography

  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.
Pages:
219-227
Main language of publication
English
Received
1999-02-03
Accepted
1999-10-30
Published
1999
Exact and natural sciences