A note on star arboricity of crowns

作者：Lee Ming Ju^*; Lin Chiang

来源：Ars Combinatoria, 2008, 88: 333-334.

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 {a(0), a(1),...a(n-1), b(0), b(1),...,b(n-1)} and edge set {a(i)b(j) : i = 0, 1,...,n-1; j equivalent to i + 1, i + 2,..., i + k (mod n)}. In [2], Lin et al. conjectured that for every k and n, 3 <= k <= n - 1, the star arboricity of the crown C-n,C-k is [k/2] + I if k is odd and rk/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(C-9t,C-4) = 3.

• 出版日期2008-7
• 单位中央民族大学