Isomorphic star decompositions of multicrowns and the power of cycles. (English) Zbl 0994.05113

Lin, Chiang; Lin, Jenq-Jong; Shyu, Tay-Woei

Ars Comb. 53, 249-256 (1999).

A crown \(C_{n,k}\) for integers \(n,k\) with \(k\leq n\) is the graph whose vertex set is \(\{a_1,\dots ,a_n, b_1,\dots ,b_n\}\) and in which each edge joins a vertex \(a_i\) for some \(i \in \{1,\dots ,n\}\) with a vertex \(b_j\), where \(j\) is congruent with someone of the numbers \(i+1,\dots ,i+k\) modulo \(n\). If each edge of \(C_{n,k}\) is replaced by \(\lambda \) edges with the same end vertices as it had, the multicrown \(\lambda C_{n,k}\) is obtained. It is proved that \(\lambda C_{nk}\) can be decomposed into copies of the star \(S_{\ell }\) with \(\ell \) edges if and only if \(\ell \leq k\) and \(\lambda _{nk} \equiv 0\) \((\text{mod} \ell)\). This implies also that the \(k\)th power of the cycle \(c_n\) of length \(n\) can be decomposed in that way if and only if \(\ell \leq k+1\) and \(nk\equiv 0\) \((\text{mod} \ell)\).

Reviewer: Bohdan Zelinka (Liberec)

MSC:

05C70

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

crown; star; decomposition