Partitioning of Trees Having Maximum Degree at Most Three

Abstract

The vertices $V$ of trees with maximum degree three and $t$ degree two vertices are partitioned into sets $R$, $B$, and $U$ such that the induced subgraphs $⟨V–R⟩$ and $⟨V–B⟩$ are isomorphic and $|U|$ is minimum. It is shown for $t\ge 2$ that there is such a partition for which $|U|=0$ if $t$ is even and $|U|=1$ if $t$ is odd. This extends earlier work by the authors which answered this problem when $t=0$ or $1$.