Edge‐decompositions of K n,n into isomorphic copies of a given tree

We study the Hä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 Kézdy and Snevily 5, that T decomposes K 2hn,2hn for some h  ≤ ⌈ r /4⌉, 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 $|V_i({v})|\ge \sqrt {2} |V_{i-1}({v})|$ , for each i  ≥ 1 with | V i ( v )| ≠ ∅ , where V i ( v ) is the set of vertices at distance i from v , then T decomposes K 2n,2n . © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 1–18, 2005