TY - JOUR

T1 - Isomorphic star decompositions of multicrowns and the power of cycles

AU - Lin, Chiang

AU - Lin, Jenq Jong

AU - Shyu, Tay Woei

PY - 1999/10

Y1 - 1999/10

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

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

UR - http://www.scopus.com/inward/record.url?scp=0040712552&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040712552&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0040712552

SN - 0381-7032

VL - 53

SP - 249

EP - 256

JO - Ars Combinatoria

JF - Ars Combinatoria

ER -