Isomorphic star decompositions of multicrowns and the power of cycles

Chiang Lin, Jenq Jong Lin, Tay Woei Shyu

Research output: Contribution to journalArticle

17 Citations (Scopus)

Abstract

For positive integers k ≤ n, the crown Cn,k is the graph with vertex set {a1, a2, ⋯, an, b1, b2, ⋯, bn} and edge set {aibj : 1 ≤ i ≤ n, j = i + 1, i + 2, ⋯, i + k (mod n)}. For any positive integer λ, the multicrown λCn,k is the multiple graph obtained from the crown Cn,k by replacing each edge e by λ edges with the same end vertices as e. A star Sl is the complete bipartite graph K1,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 λCn,k has an Sl-decomposition if and only if l ≤ k and λnk ≡ 0 (mod l). Thus, in particular, Cn,k has an Sl-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 Ckn, the k-th power of the cycle Cn, has an Sl-decomposition if and only if l ≤ k + 1 and nk ≡ 0 (mod l).

Original languageEnglish
Pages (from-to)249-256
Number of pages8
JournalArs Combinatoria
Volume53
Publication statusPublished - 1999 Oct 1
Externally publishedYes

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Isomorphic star decompositions of multicrowns and the power of cycles'. Together they form a unique fingerprint.

  • Cite this