Isomorphic star decompositions of multicrowns and the power of cycles

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/27971

Title:	Isomorphic star decompositions of multicrowns and the power of cycles
Authors:	Lin,CA;Lin,JJ;Shyu,TW
Contributors:	數學研究所
Date:	1999
Issue Date:	2010-06-29 19:39:12 (UTC+8)
Publisher:	中央大學
Abstract:	For positive integers k less than or equal to n, the. crown C-n,C- 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 less than or equal to i less than or equal to n, j = i + 1, i + 2, ... i + k (mod n)}. For any positive integer lambda, the multicrown lambda C-n,C- k is the multiple graph obtained from the crown C-n,C- 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- 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 lambda C-n,C- k has an S-l-decomposition if and only if l less than or equal to k and lambda nk = 0 (mod l). Thus, in particular, C-n,C- k has an S-l-decomposition if and only if l less than or equal to k and nk = 0 (mod l). As a consequence, we show that if n greater than or equal to 3, k < n/2, then C-n(k), the k-th power of the cycle C-n, has an S-l-decomposition if and only if l less than or equal to k + 1 and nk = 0 (mod 1).
Relation:	ARS COMBINATORIA
Appears in Collections:	[Graduate Institute of Mathematics] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	415	View/Open

社群 sharing