Decomposition of complete graphs into arbitrary trees (Q2042202)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposition of complete graphs into arbitrary trees |
scientific article |
Statements
Decomposition of complete graphs into arbitrary trees (English)
0 references
28 July 2021
0 references
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.
0 references
tree decomposition
0 references
Ringel conjecture
0 references
graph decomposition
0 references
0 references