✦ LIBER ✦

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

✍ Scribed by Anna Lladó; S.C. López

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 167 KB
Volume: 48
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20024

No coin nor oath required. For personal study only.

✦ Synopsis

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 . When a tree T of size n is not known to be bigraceful it is shown, using similar techniques to the ones by Ke ´zdy and Snevily [5], that T decomposes K 2hn;2hn for some h dr=4e, where r is the radius of T . Moreover, if the base tree of T is bigraceful or if there is a vertex v in T such that jV i ðvÞj !

📜 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