Decomposition of complete graphs into arbitrary trees

Trees (05C05) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

In this paper, the authors deal with tree-decompositions of complete graphs. A classical conjecture in the area is one by Ringel, which states that for each \(m\geq 1\) and a tree \(T\) with \(m\) edges, the complete graph \(K_{2m+1}\) can be decomposed into \(2m+1\) copies of \(T\). In this paper, the authors go further and conjecture that: \par Conjecture: For each \(m\geq 1\) and trees \(T_1\), \(T_2\) with \(|E(T_1)|=|E(T_2)|=m\), the complete graph \(K_{4m+1}\) can be decomposed into copies of \(T_1\) and \(T_2\). \par In order to support their conjecture, in the paper, the authors prove the following result which is the main one: \par Theorem: For any \(m\geq 1\) and any tree \(T\) with \(|E(T)|=m\), the complete graph \(K_{4cm+1}\) can be decomposed into copies of \(T\) and \(T_0\). Here, \(c\) is any positive constant and \(T_0\) is the path on \(m\) edges or the star on \(m\) edges.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: Decomposition of complete graphs into arbitrary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2042202)