✦ LIBER ✦

On the decomposition of n-cubes into isomorphic trees

✍ Scribed by John Frederick Fink

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 324 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140403

No coin nor oath required. For personal study only.

✦ Synopsis

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 isomorphic to members of a specified family of trees.

📜 SIMILAR VOLUMES

Decompositions of Km,n into cubes

✍ Saad El-Zanati; Charles Vanden Eynden 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

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 sho

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

The decomposition of trees into subtrees

✍ Yair Caro 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 332 KB

## Abstract A necessary condition for the decomposition of a tree __T__ into subtrees, each isomorphic to a tree from a given set of trees is presented. We also present a characterization of the set of trees for which the condition is sufficient. Many examples are given.

Random minimal spanning tree and percola

Random minimal spanning tree and percolation on the N-cube

✍ Mathew D. Penrose 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB 👁 1 views

The N-cube is a graph with 2 N vertices and N 2 Ny1 edges. Suppose indepen- dent uniform random edge weights are assigned and let T be the spanning tree of minimal Ž . y 1 N ϱ y3 total weight. Then the weight of T is asymptotic to N 2 Ý i as N ª ϱ. Asymp-is1 totics are also given for the local stru

Remarks on the placeability of isomorphi

Remarks on the placeability of isomorphic trees in a complete graph

✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 3 views

Let Tp be any tree of order p and A ( T p ) stand for the maximum degree of the vertices of Tp. We prove the following theorem. "If A(Tp) 5 pi, where p > 2i, then Tp is i-placeable in Kp" is true if and only if i = 1, 2, and 3. 0 1996 John Wiley & Sons, Inc. Suppose G is a graph and V ( G ) , E ( G

On the decomposition of kn into complete

On the decomposition of kn into complete bipartite graphs

✍ H. Tverberg 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB 👁 1 views

## Abstract A short proof is given of the impossibility of decomposing the complete graph on __n__ vertices into __n__‐2 or fewer complete bipartite graphs.