Edge-decompositions ofKn,ninto isomorphic copies of a given tree
Anna Lladó, Susana-Clara López · Journal of Graph Theory · 2004
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 Kn,n into n isomorphic copies of T. We use the concept of bigraceful labelings, introduced in 7, which give rise to cyclic decompositions of Kn,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 K2hn,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 , for each i ≥ 1 with |Vi(v)| ≠ ∅︁ , where Vi(v) is the set of vertices at distance i from v, then T decomposes K2n,2n. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 1–18, 2005