A degree bound on decomposable trees (Q2368920)

An \(n\)-vertex graph \(G=(V,E)\) is called decomposable if for any partition \((\lambda_1,\dots,\lambda_p)\) of \(n\) there exists a partition \(V_1,\dots,V_p\) of \(V\) such that \(| V_i| =\lambda_i\) and the subgraph induced by \(V_i\) is connected, \(i=1,\dots,p\). The main result of the paper is that decomposable trees have degree at most 4 and every vertex of degree 4 is adjacent to a leaf. Other results include some families of decomposable trees, and some complexity issues. In particular, a polynomial algorithm is given to decide whether a multipode (a tree with only one vertex of degree larger than 2) is decomposable.