Isomorphic star decompositions of multicrowns and the power of cycles

Chiang Lin*, Jenq Jong Lin, Tay Woei Shyu

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

21 引文 斯高帕斯(Scopus)

摘要

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).

原文英語
頁(從 - 到)249-256
頁數8
期刊Ars Combinatoria
53
出版狀態已發佈 - 1999 十月
對外發佈

ASJC Scopus subject areas

  • 數學(全部)

指紋

深入研究「Isomorphic star decompositions of multicrowns and the power of cycles」主題。共同形成了獨特的指紋。

引用此