## Abstract

For positive integers k ≤ n, the crown C_{n,k} is the graph with vertex set {a_{1}, a_{2}, ⋯, a_{n}, b_{1}, b_{2}, ⋯, b_{n}} and edge set {a_{i}b_{j} : 1 ≤ i ≤ n, j = i + 1, i + 2, ⋯, i + k (mod n)}. For any positive integer λ, the multicrown λC_{n,k} is the multiple graph obtained from the crown C_{n,k} by replacing each edge e by λ edges with the same end vertices as e. A star S_{l} is the complete bipartite graph K_{1,l}. If the edges of a graph G can be decomposed into subgraphs isomorphic to a graph H, then we say that G has an H-decomposition. In this paper, we prove that λC_{n,k} has an S_{l}-decomposition if and only if l ≤ k and λnk ≡ 0 (mod l). Thus, in particular, C_{n,k} has an S_{l}-decomposition if and only if l ≤ k and nk ≡ 0 (mod l). As a consequence, we show that if n ≥ 3, k < n/2, then C^{k}_{n}, the k-th power of the cycle C_{n}, has an S_{l}-decomposition if and only if l ≤ k + 1 and nk ≡ 0 (mod l).

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

Pages (from-to) | 249-256 |

Number of pages | 8 |

Journal | Ars Combinatoria |

Volume | 53 |

Publication status | Published - 1999 Oct 1 |

Externally published | Yes |

## ASJC Scopus subject areas

- Mathematics(all)