PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2006 | 26 | 1 | 141-147
Tytuł artykułu

Decomposing complete graphs into cubes

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
26
Numer
1
Strony
141-147
Opis fizyczny
Daty
wydano
2006
otrzymano
2005-05-05
poprawiono
2005-09-19
Twórcy
  • 4520 Mathematics Department, Illinois State University, Normal, Illinois 61790-4520, USA
  • 4520 Mathematics Department, Illinois State University, Normal, Illinois 61790-4520, USA
Bibliografia
  • [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.
  • [2] J. Bosák, Decompositions of Graphs (Kluwer Academic Publishers, 1990).
  • [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.
  • [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.
  • [5] J. Edmonds and D.R. Fulkerson, Transversals and matroid partition, J. Res. Nat. Bur. Standards 69 (B) (1965) 147-153.
  • [6] S.I. El-Zanati, M. Plantholt and C. Vanden Eynden, Graph decompositions into generalized cubes, Ars Combin. 49 (1998) 237-247.
  • [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
  • [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
  • [9] D. Froncek, Cyclic type factorizations of complete bipartite graphs into hypercubes, Australas. J. Combin. 25 (2002) 201-209.
  • [10] F. Harary and R.W. Robinson, Isomorphic factorizations X: Unsolved problems, J. Graph Theory 9 (1985) 67-86, doi: 10.1002/jgt.3190090105.
  • [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.
  • [12] A. Kotzig, Selected open problems in graph theory, in: Graph Theory and Related Topics (Academic Press, New York, 1979) 358-367.
  • [13] A. Kotzig, Decompositions of complete graphs into isomorphic cubes, J. Combin. Theory 31 (B) (1981) 292-296.
  • [14] M. Maheo, Strongly graceful graphs, Discrete Math. 29 (1980) 39-46, doi: 10.1016/0012-365X(90)90285-P.
  • [15] R.M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, in: Proc. 5th British Comb. Conf. (1975) 647-659.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1308
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.