Isomorphic Star Decompositions of Multicrowns and the Power of Cycles

For positive integers \(k \leq n\), the crown \(C_{n,k}\) is the graph with vertex set \(\{a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\}\) and edge set \(\{a_ib_j: 1 \leq j \leq n, j = i+1,i+2,\ldots,i+k \pmod{n}\}\). For any positive integer \(\lambda\), the multicrown \(\lambda C_{n,k}\) is the multiple graph obtained from the crown \(C_{n,k}\) by replacing each edge \(e\) by \(\lambda\) edges with the same end vertices as \(e\). A star \(S_l\) is the complete bipartite graph \(K_{1,k}\). 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 \(\lambda C_{n,k}\) has an \(S_l\)-decomposition if and only if \(l \leq k\) and \(\lambda nk \equiv 0 \pmod{l}\). Thus, in particular, \(C_{n,k}\) has an \(S_l\)-decomposition if and only if \(l \leq k\) and \(nk \equiv 0 \pmod{l}\). As a consequence, we show that if \(n \geq 3, k < \frac{n}{2}\) then \(C_k^n\), the \(k\)-th power of the cycle \(C_n\), has an \(S_l\)-decomposition if and only if \(1 < k+1\) and \(nk \equiv 0 \pmod{1}\).