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 \leq n\), the crown \(C_{n,k}\) is the graph with vertex set \(\{a_0, a_1, \ldots, a_{n-1}, b_0, b_1, \ldots, b_{n-1}\}\) and edge set \(\{a_ib_j: 0 \leq i \leq n-1, j = i,i+1, \ldots, i+k-1 \pmod{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 \pmod{2}\), \(n \geq 2l\) if \(t = 1\), and \(n \geq 1\) if \(t \geq 2\), (2) for \(t \geq 2\) and \(n \geq tl\), \(C_{n,tl}\) has an \(S_l(2)\)-decomposition if and only if \(nt \equiv 0 \pmod{2}\), and (3) for \(n \geq 3t\), \(C_{n,tl}\) has an \(S_3(2)\)-decomposition if and only if \(nt \equiv 0 \pmod{2}\) and \(n \equiv 0 \pmod{4}\) if \(t = 1\).