On Tree Partitions

Abstract

A splitting partition for a graph $G=(V,E)$ is a partition of $V$ into sets $R$, $B$, and $U$ so that the subgraphs induced by $V–R$ and $V–B$ are isomorphic. The splitting number $\mu (G)$ is the size of $|R|$ for any splitting partition which maximizes $|R|$. This paper determines $\mu (G)$ for trees of maximum degree at most three and exactly one degree two vertex and for trees all of whose vertices have degree three or one.