## Abstract

As usual, K_{m,n} denotes the complete bipartite graph with parts of sizes m and n. For positive integers k ≤n, the crown C_{n,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}: 0 ≤ i ≤ n - 1, j = i,i + 1,..., i + k - 1 (mod n)}. A spider is a tree with at most one vertex of degree more than two, called the center of the spider. A leg of a spider is a path from the center to a vertex of degree one. Let S_{l}(t) denote a spider of l legs, each of length t. An H-decomposition of a graph G is an edge-disjoint decomposition of G into copies of H. In this paper we investigate the problems of S _{l}(2)-decompositions of complete bipartite graphs and crowns, and prove that: (1) K_{n,tl} has an S_{l}(2)-decomposition if and only if nt ≡ 0 (mod 2), n≥ 2l if t = 1, and n ≥ J if t ≥ 2, (2) for t ≥ 2 and n ≥ tl, C_{n,tl} has an S_{l}(2)- decomposition if and only if nt ≡ 0 (mod 2), (3) for n ≥ 3t, C _{n,3t} has an S_{3}(2)-decomposition if and only if nt ≡ 0 (mod 2) and n ≡ 0 (mod 4) if t = 1.

Original language | English |
---|---|

Pages (from-to) | 239-248 |

Number of pages | 10 |

Journal | Ars Combinatoria |

Volume | 112 |

Publication status | Published - 2013 Oct |

## Keywords

- Complete bipartite graph
- Crown
- Decomposition
- Spider

## ASJC Scopus subject areas

- Mathematics(all)