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 < k < n, the crown Cn>k is the graph with vertex set {ao,ai, an-i,b0,bi,&i} and edge set {a,ibj : i = 0,1,n 1; j = i + 1,i + 2, ,i + k (mod n)}. In [2], Lin et al. conjectured that for every k and n, 2> < k < n - 1, the star arboricity of the crown CUik is f/c/2] + 1 if k is odd and k/2] + 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(Cgt,4) = 3.
展开▼
