DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 26(2) (2006) 351
DOI: 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 K2n be a complete graph and T a tree, both with 2n vertices. A T-factorization of K2n is a collection of edge disjoint spanning subgraphs (i.e., factors) T1,T2,... ,Tn of K2n, all isomorphic to T. Every edge of K2n then appears in exactly one copy of T.

     M. Kubesa asked the following question: Suppose that there exists a T-factorization of K2n. 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 ∈ Xdeg(x) = ∑y ∈ Ydeg(y) ?

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