Decomposing complete graphs into cubes

Saad I. El-Zanati; C. Vanden Eynden

Discussiones Mathematicae Graph Theory, Tome 26 (2006), p. 141-147 / Harvested from The Polish Digital Mathematics Library

Access to full text
Full (PDF)

Résumé

This paper concerns when the complete graph on n vertices can be decomposed into d-dimensional cubes, where d is odd and n is even. (All other cases have been settled.) Necessary conditions are that n be congruent to 1 modulo d and 0 modulo $2^{d}$ . These are known to be sufficient for d equal to 3 or 5. For larger values of d, the necessary conditions are asymptotically sufficient by Wilson’s results. We prove that for each odd d there is an infinite arithmetic progression of even integers n for which a decomposition exists. This lends further weight to a long-standing conjecture of Kotzig.

Publié le : 2006-01-01

Zbl 1131.05072

EUDML-ID : urn:eudml:doc:270613

@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1308,
     author = {Saad I. El-Zanati and C. Vanden Eynden},
     title = {Decomposing complete graphs into cubes},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {26},
     year = {2006},
     pages = {141-147},
     zbl = {1131.05072},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1308}
}

Saad I. El-Zanati; C. Vanden Eynden. Decomposing complete graphs into cubes. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 141-147. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1308/

Bibliographie

[000] [1] P. Adams, D. Bryant and B. Maenhaut, Cube Factorizations of Complete Graphs, J. Combin. Designs 12 (2004) 381-388, doi: 10.1002/jcd.20015. | Zbl 1053.05099

[001] [2] J. Bosák, Decompositions of Graphs (Kluwer Academic Publishers, 1990). | Zbl 0701.05042

[002] [3] D. Bryant, S.I. El-Zanati and R. Gardner, Decompositions of $K_{m, n}$ and Kₙ into cubes, Australas. J. Combin. 9 (1994) 285-290. | Zbl 0809.05076

[003] [4] D. Bryant, S.I. El-Zanati, B. Maenhaut and C. Vanden Eynden, Decomposition of complete graphs into 5-cubes, J. Combin. Designs, to appear. | Zbl 1087.05046

[004] [5] J. Edmonds and D.R. Fulkerson, Transversals and matroid partition, J. Res. Nat. Bur. Standards 69 (B) (1965) 147-153. | Zbl 0141.21801

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

[006] [7] S.I. El-Zanati and C. Vanden Eynden, Decompositions of $K_{m, n}$ into cubes, J. Combin. Designs 4 (1996) 51-57, doi: 10.1002/(SICI)1520-6610(1996)4:1<51::AID-JCD5>3.0.CO;2-Z | Zbl 0913.05080

[007] [8] S.I. El-Zanati and C. Vanden Eynden, Factorizations of complete multipartite graphs into generalized cubes, J. Graph Theory 33 (2000) 144-150, doi: 10.1002/(SICI)1097-0118(200003)33:3<144::AID-JGT4>3.0.CO;2-P | Zbl 0940.05055

[008] [9] D. Froncek, Cyclic type factorizations of complete bipartite graphs into hypercubes, Australas. J. Combin. 25 (2002) 201-209. | Zbl 1017.05084

[009] [10] F. Harary and R.W. Robinson, Isomorphic factorizations X: Unsolved problems, J. Graph Theory 9 (1985) 67-86, doi: 10.1002/jgt.3190090105. | Zbl 0617.05051

[010] [11] K. Heinrich, Graph decompositions and designs, in: The CRC handbook of combinatorial designs. Edited by Charles J. Colbourn and Jeffrey H. Dinitz. CRC Press Series on Discrete Mathematics and its Applications (CRC Press, Boca Raton, FL, 1996) 361-366. | Zbl 0881.05105

[011] [12] A. Kotzig, Selected open problems in graph theory, in: Graph Theory and Related Topics (Academic Press, New York, 1979) 358-367.

[012] [13] A. Kotzig, Decompositions of complete graphs into isomorphic cubes, J. Combin. Theory 31 (B) (1981) 292-296. | Zbl 0496.05041

[013] [14] M. Maheo, Strongly graceful graphs, Discrete Math. 29 (1980) 39-46, doi: 10.1016/0012-365X(90)90285-P.

[014] [15] R.M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, in: Proc. 5th British Comb. Conf. (1975) 647-659.