Partitioning Graphs into Induced Stars

Abstract

A partition $\mathcal{D}=\{V_1,\dots ,V_m\}$ of the vertex set $V(G)$ of a graph $G$ is said to be a star decomposition if each $V_i$ ($1\le i\le m$) induces a star of order at least two.
In this note, we prove that a connected graph $G$ has a star decomposition if and only if $G$ has a block which is not a complete graph of odd order.