# Multidecompositions of the Balanced Complete Bipartite Graph into Paths and Stars

Authors: Hung-Chih Lee; Yen-Po Chu
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

LetPk and Sk denote a path and a star with k edges, respectively. For graphs F, G, and H, a (G,H)-multidecomposition of F is a partition of the edge set of F into copies of G and copies of H with at least one copy of G and at least one copy of H. In this paper, necessary and sufficient conditions for the existence of the (Pk, Sk)-multidecomposition of the balanced complete bipartite graph are given.


---

## Body

## 1. Introduction

LetF, G, and H be graphs. A G-decomposition of F is a partition of the edge set of F into copies of G. If F has a G-decomposition, we say that F is G-decomposable and write G∣F. A (G,H)-multidecomposition of F is a partition of the edge set of F into copies of G and copies of H with at least one copy of G and at least one copy of H. If F has a (G,H)-multidecomposition, we say that F is (G,H)-multidecomposable and write (G,H)∣F.For positive integersm and n, Km,n denotes the complete bipartite graph with parts of sizes m and n. A complete bipartite graph is balanced if m=n. A k-path, denoted by Pk, is a path with k edges. A k-star, denoted by Sk, is the complete bipartite graph K1,k. A k-cycle, denoted by Ck, is a cycle of length k.P
k-decompositions of graphs have been a popular topic of research in graph theory. Articles of interest include [1–11]. The reader can refer to [12] for an excellent survey of this topic. Decompositions of graphs into k-stars have also attracted a fair share of interest. Articles of interest include  [13–18]. The study of the (G,H)-multidecomposition was introduced by Abueida and Daven in [19]. Abueida and Daven [20] investigated the problem of the (Kk,Sk)-multidecomposition of the complete graph Kn. Abueida and Daven [21] investigated the problem of the (C4,E2)-multidecomposition of several graph products where E2 denotes two vertex disjoint edges. Abueida and O'Neil [22] settled the existence problem of the (Ck,Sk-1)-multidecomposition of the complete multigraph λKn for k=3,4, and 5. In [23], Priyadharsini and Muthusamy gave necessary and sufficient conditions for the existence of the (Gn,Hn)-multidecomposition of λKn where Gn,Hn∈{Cn,Pn-1,Sn-1}. Furthermore, Shyu [24] investigated the problem of decomposing Kn into k-paths and k-stars, and gave a necessary and sufficient condition for k=3. In [25], Shyu considered the existence of a decomposition of Kn into k-paths and k-cycles and established a necessary and sufficient condition for k=4. He also gave criteria for the existence of a decomposition of Kn into 3-paths and 3 cycles in [26]. Shyu [27] investigated the problem of decomposing Kn into k-cycles and k-stars and settled the case k=4. Recently, Lee [28] established necessary and sufficient conditions for the existence of the (Ck,Sk)-multidecomposition of a complete bipartite graph.In this paper, we investigate the problem of the(Pk,Sk)-multidecomposition of the balanced complete bipartite graph and give necessary and sufficient conditions for such a multidecomposition to exist.


## 2. Preliminaries

For our discussions, some terminologies and notations are needed. LetG be a graph. The degree of a vertex x of G, denoted by degGx, is the number of edges incident with x. A graph is r-regular if each vertex is of degree r. The vertex of degree k in Sk is called the center of Sk. Let V and E be subsets of the vertex set and the edge set of G, respectively. We use G[V] to denote the subgraph of G induced by V and G-E to denote the subgraph obtained from G by deleting E. Suppose that G1,G2,…,Gt are edge-disjoint-graphs. Then, G1+G2+⋯+Gt, or ∑i=1t‍Gi, denotes the graph H with vertex set V(H)=⋃i=1t‍V(Gi), and edge set E(H)=⋃i=1t‍E(Gi). Thus, if a graph H can be decomposed into subgraphs G1,G2,…,Gt, we write H=G1+G2+⋯+Gt, or H=∑i=1t‍Gi. Moreover, ⌈x⌉ denotes the smallest integer not less than x and ⌊x⌋ denotes the largest integer not greater than x. Let v0v1v2,…,vk denote the k-path with edges v0v1,v1v2,…,vk-1vk, and (v1,v2,…,vk) denote the k-cycle with edges v1v2,v2v3,…,vk-1vk,vkv1. Throughout the paper, (A,B) denotes the bipartition of Kn,n, where A={a0,a1,…,an-1} and B={b0,b1,…,bn-1}.For the edgeaibj in Kn,n, the  label of aibj is j-i(modn). For example, in K9,9 the labels of a3b7 and a8b2 are 4 and 3, respectively. Note that each vertex of Kn,n is incident with exactly one edge with label i for i=0,1,2,…,n-1. Let G be a subgraph of Kn,n and t a nonnegative integer. We use G+t to denote the graph with vertex set {ai:ai∈V(G)}⋃‍{bj+t:bj∈V(G)} and edge set {aibj+t:aibj∈E(G)}, where the subscripts of b are taken modulo n. In particular, G+0=G.The following results due to Yamamoto et al. and Parker, respectively, are essential for our discussions.Proposition 1 (see [18]).
Letm≥n≥1 be integers. Then, Km,n is Sk-decomposable if and only if m≥k and
(1)m≡0(modk)ifn<k,mn≡0(modk)ifn≥k.Proposition 2 (see [7]).
There exists aPk-decomposition of Km,n if and only if mn≡0(modk),  and one of aforementioned  (see Table 1) cases occurs.Table 1
Case
k
m
n
Conditions
1
Even
Even
Even
k
≤
2
m, k≤2n, both are not  equalities
2
Even
Even
Odd
k
≤
2
m
-
2, k≤2n
3
Even
Odd
Even
k
≤
2
m, k≤2n-2
4
Odd
Even
Even
k
≤
2
m
-
1, k≤2n-1
5
Odd
Even
Odd
k
≤
2
m
-
1, k≤n
6
Odd
Odd
Even
k
≤
m, k≤2n-1
7
Odd
Odd
Odd
k
≤
m, k≤n


## 3. Main Results

We first give necessary conditions of the(Pk,Sk)-multidecomposition of Kn,n.Lemma 3.
Letk and n be positive integers. If there exists a (Pk,Sk)-multidecomposition of Kn,n, then k≤n and n2≡0(modk).Proof.
The result follows from the fact that the maximum size of a star inKn,n is n, the size of each member in the multidecomposition is k, and |E(Kn,n)|=n2.We now show that the necessary conditions are also sufficient. SincePk=Sk for k=1,2, the result holds for k=1,2 by Proposition 1. So it remains to consider the case k≥3. The proof is divided into cases n≥2k, n=k and k<n<2k, which are treated in Lemmas 4,  5, and 6, respectively.Lemma 4.
Letk and n be positive integers with n≥2k≥6. If n2≡0(modk), then Kn,n is (Pk,Sk)-multidecomposable.Proof.
Letn=qk+r where q and r are integers with 0≤r<k. Then, q≥2 from the assumption n≥2k. Note that
(2)Kn,n=Kqk+r,n=K(q-1)k,n+Kk+r,n.
By Proposition 1, K(q-1)k,n is Sk-decomposable. On the other hand, trivially, k≤min{k+r,n}, and |E(Kk+r,n)|=(k+r)n≡0(modk) from the assumption n2≡0(modk). This implies that Kk+r,n is Pk-decomposable by Proposition 2. Hence, Kn,n is (Pk,Sk)-multidecomposable.Lemma 5.
Letk be a positive integer with k≥3. Then, Kk,k is (Pk,Sk)-multidecomposable.Proof.
Note thatKk,k=K1,k+Kk-1,k. Trivially, K1,k=Sk. On the other hand, |E(Kk-1,k)|=(k-1)k≡0(modk). Furthermore, k≤2(k-1)-1 for odd k, and k≤2(k-1)=2k-2 for even k. Hence, Kk-1,k is Pk-decomposable by Proposition 2, and Kk,k is (Pk,Sk)-multidecomposable.Lemma 6.
Letk and n be integers with 3≤k<n<2k. If n2≡0(modk), then Kn,n is (Pk,Sk)-multidecomposable.Proof.
Suppose thatn=k+r. Then, 0<r<k from the assumption k<n<2k. Let A1={a0,a1,…,ak-1}, B1={b0,b1,…,bk-1}, A2={ak,ak+1,…,ak+r-1}, and B2={bk,bk+1,…,bk+r-1}. Let Gi=Kn,n[Ai∪B1] for i=1,2 and H=Kn,n[A∪B2]. Then, Kn,n=G1+G2+H. Note that G1 is isomorphic to Kk,k, H is isomorphic to Kk+r,r, and G2 is isomorphic to Kr,k, which is Sk-decomposable by Proposition 1. Hence, it is sufficient to show that G1+H is (Pk,Sk)-multidecomposable.
Lett=r2/k. Since k∣n2, we have k∣r2, which implies that t is a positive integer  Let C=(b0,a0,b1,a1,…,bk-2,ak-2,bk-1,ak-1). Then, C is a 2k-cycle in G1. Let p=⌊t/2⌋. For odd t, define a k-path P in G1 as follows:
(3)P={b2pa0b2p+1a1⋯b2p-1+k/2ak/2-1b2p+k/2ifkiseven,b2pa0b2p+1a1⋯b2p+(k-1)/2a(k-1)/2ifkisodd,
where the subscripts of b are taken modulo k. Since t=r2/k and r<k, we have
(4)t≤r-1≤k-2.
Thus, 2p+1=t≤k-2, which implies the labels of the edges in P are 2p and 2p+1. Note that for i=0,1,…,p-1, C+2i is a 2k-cycle which consists of all of the edges with labels 2i and 2i+1 in G1. Thus, C,C+2,…,C+2(p-1) and P are edge-disjoint in G1.
Define a subgraphW of G1 as follows:
(5)W={∑i=0p-1C+2iforevent,∑i=0p-1C+2i+Pforoddt≥3,Pfort=1.
Since C2k can be decomposed into 2 copies of Pk and 2p=t for even t as well as 2p+1=t for odd t, W can be decomposed into t copies of Pk. Let δ=1 for even k and δ=0 for odd k. Note that for even t, degG1-E(W)ai=k-2p=k-t, and for odd t,
(6)degG1-E(W)ai={k-t-1ifi=0,1,…,⌈k2⌉-2,k-t-δifi=⌈k2⌉-1,k-t+1ifi=⌈k2⌉,⌈k2⌉+1,…,k-1.
Let Xi=(G1-E(W))[{ai}∪B1] for i=0,1,…,k-1. Then for even t, Xi=Sk-t, and for odd t,
(7)Xi={Sk-t-1ifi=0,1,…,⌈k2⌉-2,Sk-t-δifi=⌈k2⌉-1,Sk-t+1ifi=⌈k2⌉,⌈k2⌉+1,…,k-1
with the center at ai. In the following, we will show that H can be decomposed into r copies of Sk with centers in B2, and into k copies of St with centers in A1 for even t, and into ⌈k/2⌉-1 copies of St+1 with centers in {a0,a1,…,a⌈k/2⌉-2}, an St+δ with the center at a⌈k/2⌉-1, and k-⌈k/2⌉ copies of St-1 with centers in {a⌈k/2⌉,a⌈k/2⌉+1,…,ak-1} for odd t.
We show the required star decomposition ofH by orienting the edges of H. For any vertex x of H, the outdegree degH+x (indegree degH-x, resp.) of x in an orientation of H is the number of arcs incident from (to, resp.) x. It is sufficient to show that there exists an orientation of H such that
(8)degH+bj=k,
where j=k,k+1,…,k+r-1, and for even t(9)degH+ai=t,
where i=0,1,…,k-1, and for odd t(10)degH+ai={t+1ifi=0,1,…,⌈k2⌉-2,t+δifi=⌈k2⌉-1,t-1ifi=⌈k2⌉,⌈k2⌉+1,…,k-1.
We first consider the edges oriented outward fromA1 according to the parity of t. Let β=k+(t+1)(⌈k/2⌉-1) and γ=β+t+δ. If t is even, then the edges aibk+ti,aibk+ti+1,…,aibk+ti+t-1 are all oriented outward from ai, where i=0,1,…,k-1. If t is odd, then the edges aibk+(t+1)i,aibk+(t+1)i+1,…,aibk+(t+1)i+t for i=0,1,…,⌈k/2⌉-2, and a⌈k/2⌉-1bβ,a⌈k/2⌉-1bβ+1,…, a⌈k/2⌉-1bβ+t+δ-1, as well as aib(t-1)(i-⌈k/2⌉)+γ,aib(t-1)(i-⌈k/2⌉)+γ+1,…,aib(t-1)(i-⌈k/2⌉)+γ+t-2 for i=⌈k/2⌉,⌈k/2⌉+1,…,k-1 are all oriented outward from ai. In both cases, the subscripts of b are taken modulo r in the set of numbers {k,k+1,…,k+r-1}. Note that for even t we orient t edges from each ai and for odd t we orient at most t+1 edges from ai. By inequality (4), we have t+1≤r, which assures us that there are enough edges for the above orientation.
Finally, the edges which are not oriented yet are all oriented fromB2 to A. From the construction of the orientation, it is easy to see that (9) and (10) are satisfied, and for all bw,bw′∈B2, we have
(11)|degH-bw-degH-bw′|≤1.
So, we only need to check (8).
SincedegH+bw+degH-bw=k+r for bw∈B2, it follows from (11) that
(12)|degH+bw-degH+bw′|≤1
for bw,bw′∈B2. Note that for even t, ∑i=0k-1‍degH+ai=tk, and for odd t,
(13)∑i=0k-1‍degH+ai=(t+1)(⌈k2⌉-1)+t+δ+(t-1)(k-⌈k2⌉)=(t-1)k+2(⌈k2⌉)-1+δ={(t-1)k+2(k2)-1+1ifkiseven,(t-1)k+2(k+1)2-1ifkisodd.=tk.
Thus,
(14)∑w=kk+r-1‍degH+bw=|E(Kk+r,r)|-∑i=0k-1‍degH+ai=(k+r)r-tk=kr+r2-r2=kr.
Therefore from (12), we have degH+bw=k for bw∈B2. This establishes (8). Hence, there exists the required decomposition 𝒟of H. Let Xi′ be the star with center at ai in 𝒟 for i=0,1,…,k-1. Then, Xi+Xi′ is a k-star. This completes the proof.Now, we are ready for the main result. It is obtained form the arguments above, Lemma4 and Lemmas 3, 4, 5, and 6.Theorem 7.
Letk and n be positive integers. Then, Kn,n has a (Pk,Sk)-multidecomposition if and only if k≤n and n2≡0(modk).



---

*Source: 398473-2013-03-11.xml*