A Note on Star Arboricity of Crowns

Abstract

The \({star arboricity}\) \(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 \leq k \leq n\), the \({crown}\) \(C_{n,k}\) is the graph with vertex set \(\{a_0, a_1, \ldots, a_{n-1}, b_0, b_1, \ldots, b_{n-1}\}\) and edge set \(\{a_ib_j : i = 0, 1, \ldots, n-1, j \equiv i+1, i+2, \ldots, i+k \pmod{n}\}\). In \([2]\), Lin et al. conjectured that for every \(k\) and \(n\), \(3 \leq k \leq 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\).