Decomposing complete graphs into cubes

Saad I. El-Zanati; C. Vanden Eynden

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 1, page 141-147
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Saad I. El-Zanati, and C. Vanden Eynden. "Decomposing complete graphs into cubes." Discussiones Mathematicae Graph Theory 26.1 (2006): 141-147. <http://eudml.org/doc/270613>.

@article{SaadI2006,
abstract = {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.},
author = {Saad I. El-Zanati, C. Vanden Eynden},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph decomposition; graph factorization; d-cube},
language = {eng},
number = {1},
pages = {141-147},
title = {Decomposing complete graphs into cubes},
url = {http://eudml.org/doc/270613},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Saad I. El-Zanati
AU - C. Vanden Eynden
TI - Decomposing complete graphs into cubes
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 1
SP - 141
EP - 147
AB - 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.
LA - eng
KW - graph decomposition; graph factorization; d-cube
UR - http://eudml.org/doc/270613
ER -

References

top
  1. [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. Zbl1053.05099
  2. [2] J. Bosák, Decompositions of Graphs (Kluwer Academic Publishers, 1990). Zbl0701.05042
  3. [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. Zbl0809.05076
  4. [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. Zbl1087.05046
  5. [5] J. Edmonds and D.R. Fulkerson, Transversals and matroid partition, J. Res. Nat. Bur. Standards 69 (B) (1965) 147-153. Zbl0141.21801
  6. [6] S.I. El-Zanati, M. Plantholt and C. Vanden Eynden, Graph decompositions into generalized cubes, Ars Combin. 49 (1998) 237-247. 
  7. [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 Zbl0913.05080
  8. [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 Zbl0940.05055
  9. [9] D. Froncek, Cyclic type factorizations of complete bipartite graphs into hypercubes, Australas. J. Combin. 25 (2002) 201-209. Zbl1017.05084
  10. [10] F. Harary and R.W. Robinson, Isomorphic factorizations X: Unsolved problems, J. Graph Theory 9 (1985) 67-86, doi: 10.1002/jgt.3190090105. Zbl0617.05051
  11. [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. Zbl0881.05105
  12. [12] A. Kotzig, Selected open problems in graph theory, in: Graph Theory and Related Topics (Academic Press, New York, 1979) 358-367. 
  13. [13] A. Kotzig, Decompositions of complete graphs into isomorphic cubes, J. Combin. Theory 31 (B) (1981) 292-296. Zbl0496.05041
  14. [14] M. Maheo, Strongly graceful graphs, Discrete Math. 29 (1980) 39-46, doi: 10.1016/0012-365X(90)90285-P. 
  15. [15] R.M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, in: Proc. 5th British Comb. Conf. (1975) 647-659. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.