TY - JOUR

T1 - Decomposition of bipartite graphs into spiders all of whose legs are two in length

AU - Shyu, Tay Woei

AU - Chen, Ying Ren

AU - Lin, Chiang

AU - Zhong, Ming Hong

PY - 2013/10

Y1 - 2013/10

N2 - As usual, Km,n denotes the complete bipartite graph with parts of sizes m and n. For positive integers k ≤n, the crown Cn,k is the graph with vertex set {a0, a1,..., an-1, b0, b1,...,bn-1} and edge set {a ibj: 0 ≤ i ≤ n - 1, j = i,i + 1,..., i + k - 1 (mod n)}. A spider is a tree with at most one vertex of degree more than two, called the center of the spider. A leg of a spider is a path from the center to a vertex of degree one. Let Sl(t) denote a spider of l legs, each of length t. An H-decomposition of a graph G is an edge-disjoint decomposition of G into copies of H. In this paper we investigate the problems of S l(2)-decompositions of complete bipartite graphs and crowns, and prove that: (1) Kn,tl has an Sl(2)-decomposition if and only if nt ≡ 0 (mod 2), n≥ 2l if t = 1, and n ≥ J if t ≥ 2, (2) for t ≥ 2 and n ≥ tl, Cn,tl has an Sl(2)- decomposition if and only if nt ≡ 0 (mod 2), (3) for n ≥ 3t, C n,3t has an S3(2)-decomposition if and only if nt ≡ 0 (mod 2) and n ≡ 0 (mod 4) if t = 1.

AB - As usual, Km,n denotes the complete bipartite graph with parts of sizes m and n. For positive integers k ≤n, the crown Cn,k is the graph with vertex set {a0, a1,..., an-1, b0, b1,...,bn-1} and edge set {a ibj: 0 ≤ i ≤ n - 1, j = i,i + 1,..., i + k - 1 (mod n)}. A spider is a tree with at most one vertex of degree more than two, called the center of the spider. A leg of a spider is a path from the center to a vertex of degree one. Let Sl(t) denote a spider of l legs, each of length t. An H-decomposition of a graph G is an edge-disjoint decomposition of G into copies of H. In this paper we investigate the problems of S l(2)-decompositions of complete bipartite graphs and crowns, and prove that: (1) Kn,tl has an Sl(2)-decomposition if and only if nt ≡ 0 (mod 2), n≥ 2l if t = 1, and n ≥ J if t ≥ 2, (2) for t ≥ 2 and n ≥ tl, Cn,tl has an Sl(2)- decomposition if and only if nt ≡ 0 (mod 2), (3) for n ≥ 3t, C n,3t has an S3(2)-decomposition if and only if nt ≡ 0 (mod 2) and n ≡ 0 (mod 4) if t = 1.

KW - Complete bipartite graph

KW - Crown

KW - Decomposition

KW - Spider

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

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

M3 - Article

AN - SCOPUS:84901767343

SN - 0381-7032

VL - 112

SP - 239

EP - 248

JO - Ars Combinatoria

JF - Ars Combinatoria

ER -