DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(2) (1999) 219-227
DOI: 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 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 Q4.

Keywords: hypercubes, bipartite graphs, factorization.

1991 Mathematics Subject Classification: 05C70.

References

[1] S. El-Zanati and C. Vanden Eynden, Decompositions of Km,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