DMGT

Discussiones Mathematicae Graph Theory 26(2) (2006) 351
DOI: https://doi.org/10.7151/dmgt.1326

PROBLEM PRESENTED AT THE WORKSHOP IN KRYNICA 2004

This is a problem by Michael Kubesa, Technical University Ostrava, presented by Dalibor Froncek.

Let K_2n be a complete graph and T a tree, both with 2n vertices. A T-factorization of K_2n is a collection of edge disjoint spanning subgraphs (i.e., factors) T₁,T₂,... ,T_n of K_2n, all isomorphic to T. Every edge of K_2n then appears in exactly one copy of T.

M. Kubesa asked the following question: Suppose that there exists a T-factorization of K_2n. Is it then true that the vertex set of T can be decomposed into two subsets, X and Y, such that

(1)

|X| = |Y| = n,

(2)

∑_{x ∈ X}deg(x) = ∑_{y ∈ Y}deg(y) ?

Notice that the sets X,Y in general are not the partite sets of the bipartition of T.