✦ LIBER ✦

Decompositions of Km,n into cubes

✍ Scribed by Saad El-Zanati; Charles Vanden Eynden

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 384 KB
Volume: 4
Category: Article
ISSN: 1063-8539
DOI: 10.1002/(sici)1520-6610(1996)4:1<51::aid-jcd5>3.0.co;2-z

No coin nor oath required. For personal study only.

✦ Synopsis

For a complete bipartite graph to be decomposable into isomorphic cubes, certain conditions on the number of cube and bipartition vertices must hold. We prove these necessary conditions sufficient in some cases. For cubes of fixed dimension d (indeed for d-regular bipartite graphs in general) we show that proving sufficiency can be reduced to decomposing a finite number of complete bipartite graphs. When t = 2d-' and r is the remainder on dividing t by d, we

show Kr,r is decomposable into d-cubes and an r-factor, where if r > 0 this r-factor itself is decomposable into r-cubes.

📜 SIMILAR VOLUMES

On the decomposition of n-cubes into iso

On the decomposition of n-cubes into isomorphic trees

✍ John Frederick Fink 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB

## Abstract We prove that if T is any tree having __n__ edges (__n__ ≥ 1), then the __n__‐cube Q~n~ can be decomposed into 2^n‐1^ edge‐disjoint induced subgraphs, each of which is isomorphic to T. We use this statement to obtain two results concerning decompositions of Q~n~ into subgraphs isomorphi

Decomposition of complete graphs into 5-

Decomposition of complete graphs into 5-cubes

✍ D. Bryant; S. I. El-Zanati; B. Maenhaut; C. Vanden Eynden 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB

## Abstract Necessary conditions for the complete graph on __n__ vertices to have a decomposition into 5‐cubes are that 5 divides __n__ − 1 and 80 divides __n__(__n__ − 1)/2. These are known to be sufficient when __n__ is odd. We prove them also sufficient for __n__ even, thus completing the spectr

Decompositions of graphs into trees

✍ Zbigniew Lonc 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 460 KB

Edge-decompositions of Kn,n into isomorp

Edge-decompositions of Kn,n into isomorphic copies of a given tree

✍ Anna Lladó; S.C. López 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB

We study the Ha ¨ggkvist conjecture which states that, for each tree T with n edges, there is an edge-partition of the complete bipartite graph K n;n into n isomorphic copies of T . We use the concept of bigraceful labelings, introduced in [7], which give rise to cyclic decompositions of K n;n . Whe

Factorizations of complete multipartite

Factorizations of complete multipartite graphs into generalized cubes

✍ El--Zanati, S.; Vanden Eynden, C. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 views

For a positive integer d, the usual d-dimensional cube Q d is defined to be the graph (K 2 ) d , the Cartesian product of d copies of K 2 . We define the generalized cube Q(K k , d) to be the graph (K k ) d for positive integers d and k. We investigate the decomposition of the complete multipartite

New regular embeddings of n-cubes Qn

✍ Young Soo Kwon 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB

## Abstract We investigate highly symmetrical embeddings of the __n__‐dimensional cube __Q__~__n__~ into orientable compact surfaces which we call regular embeddings of __Q__~__n__~. We derive some general results and construct some new families of regular embeddings of __Q__~__n__~. In particular,