A Note on Star Arboricity of Crowns

Abstract

The $stararboricity$ $sa(G)$ of a graph $G$ is the minimum number of star forests which are needed to decompose all edges of $G$. For integers $k$ and $n$, $1\le k\le n$, the $crown$ $C_{n,k}$ is the graph with vertex set $\{a_0,a_1,\dots ,a_{n-1},b_0,b_1,\dots ,b_{n-1}\}$ and edge set $\{a_i{b}_j:i=0,1,\dots ,n-1,j\equiv i+1,i+2,\dots ,i+k(\mathrm{mod}n)\}$. In $[2]$, Lin et al. conjectured that for every $k$ and $n$, $3\le k\le n-1$, the star arboricity of the crown $C_{n,k}$ is $\lceil k/2\rceil +1$ if $k$ is odd and $\lceil k/2\rceil +2$ otherwise. In this note, we show that the above conjecture is not true for the case $n=9t$ ($t$ is a positive integer) and $k=4$ by showing that $sa(C_{9t,4})=3$.