Decomposition of Bipartite Graphs Into Spiders All of Whose Legs Are Two in Length

Abstract

As usual, $K_{m,n}$ denotes the complete bipartite graph with parts of sizes $m$ and $n$. For positive integers $k\le n$, the crown $C_{n,k}$ is the graph with vertex set $\{a_0,a_1,\dots ,a_{n-1},b_0,b_1,\dots ,b_{n-1}\}$ and edge set $\{a_i{b}_j:0\le i\le n-1,j=i,i+1,\dots ,i+k-1(\mathrm{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 $S_l(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) $K_{n,tl}$ has an $S_l(2)$-decomposition if and only if $nt\equiv 0(\mathrm{mod}2)$, $n\ge 2l$ if $t=1$, and $n\ge 1$ if $t\ge 2$, (2) for $t\ge 2$ and $n\ge tl$, $C_{n,tl}$ has an $S_l(2)$-decomposition if and only if $nt\equiv 0(\mathrm{mod}2)$, and (3) for $n\ge 3t$, $C_{n,tl}$ has an $S_3(2)$-decomposition if and only if $nt\equiv 0(\mathrm{mod}2)$ and $n\equiv 0(\mathrm{mod}4)$ if $t=1$.