Ratio Mathematica Volume 41, 2021, pp. 45-52 On decomposition of multistars into multistars Reji T* Ruby R† Abstract The multistar Sw1,...,wn is the multigraph whose underlying graph is an n-star and the multiplicities of its n edges are w1, ...,wn. Let G and H be two multigraphs. An H-decomposition of G is a set D of H-subgraphs of G, such that the sum of ω(e) over all graphs in D which include an edge e, equals the multiplicity of e in G, for all edges e in G. In this paper, we fully characterize S1,2,3,K1,m and Sm l decomposable multistars, where ml is m repeated l times. Keywords: decomposition; multigraph; multistar 2020 AMS subject classifications: 05C51; 05C70; 05C75 1 *Department of Mathematics, Government College, Chittur, Palakkad, Kerala, India-678104; rejiaran@gmail.com. †Department of Mathematics, Government College, Chittur, Palakkad, Kerala, India-678104; rubymathpkd@gmail.com. 1Received on October 24, 2021. Accepted on November 24, 2021. Published on December 31, 2021. doi: 10.23755/rm.v41i0.681. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published under the CC-BY licence agreement. 45 Reji T, Ruby R 1 Introduction If G and H are two simple graphs with out isolated vertices, then G is H- decomposable or H divides G if there exists a partition of the edge set of G into disjoint isomorphic copies of H. The above definition can be extended to mutigraphs also. Let G and H be two multigraphs. Then the corresponding H-decomposition problem is to decide for a fixed H and an input G, whether such a partition exists. We can formally define the concepts about multigraphs and the multigraph decomposition problems as follows. Definition 1.1. A multigraph (V,E,w) consists of a simple underlying graph (V,E) and a multiplicity function w : E → N, where N is the set of natural numbers. The multigraph on an underlying graph G with constant multiplicity λ is de- noted by λ.G and this is different from λG, denoting λ disjoint copies of G. When referring to a simple graph G as a multigraph we mean 1.G. An isomophism between multigraphs is an isomophism between their underlying simple graphs which peserves edge multiplicity. Definition 1.2. A subgraph H of a multigraph G is a multigraph H whose under- lying graph is a subgraph of that of G and its multiplicity function is dominated by the multiplicity function of G, i.e. the multiplicity of an edge in H does not exceed its multiplicity in G. Definition 1.3. An H-subgraph of G is a subgraph of a multigraph G, isomorphic to a multigraph H. Definition 1.4. Let G and H be two multigraphs. An H-decomposition of G is a set D of H-subgraphs of G, such that the sum of ω(e) over all graphs in D which include an edge e, equals the multiplicity of e in G, for all edges e in G. Definition 1.5. The multistar Sw1,w2,··· ,wn is the multigraph whose underlying graph is an n-star and the multiplicities of its n edges are w1,w2, · · · ,wn. There are considerable number of papers dealing with an H-decomposition of G and some them are provided in the reference [Shyu, 2013, Lin and Shyu, 1996, Lin, 2010, Lee and Lin, 2005, Lee et al., 2005, Bryant et al., 2001, Bialostocki and Roditty, 1982]. Priesler and Tarsi [Priesler and Tarsi, 2004] showed that, for any multistar H (except a few cases), H-decomposition is NP -complete. Priesler and Tarsi [Priesler and Tarsi, 2005] fully characterized S1,2-decomposable multistars in the following theorem. 46 On decomposition of multistars into multistars Theorem 1.1. [Priesler and Tarsi, 2005] The multistar Sw1,w2,··· ,wn , n ≥ 2 is S1,2-decomposable if and only if 1. Σni=1wi ≡ 0(mod 3) 2. The number of odd multiplicities among the wi is at most 1 3 (Σni=1wi) 3. The largest among the wi is at most twice the sum of all the others. In this paper we fully characterize those multistars which are S1,2,3-decomposable, K1,m-decomposable, S2 m -decomposable and Sm l -decomposable where ml de- notes m repeated l times. 2 Main Results 2.1 S1,2,3 decomposability of Sw1,w2,w3 Theorem 2.1. Let w1 ≥ w2 ≥ w3 ≥ 2 be positive integers and n = w1+w2+w36 . Then Sw1,w2,w3 is S1,2,3-decomposable if 1. w1 + w2 + w3 ≡ 0(mod 6) 2. 2 ≤ w1 −n ≤ 2n, 2 ≤ w2 −n ≤ 2n 3. 5w2 ≤ w1 + 7w3 − 12 4. w1 ≤ w2 +w3−6 if m and l−( m−12 ) are odd where m = w1−n,l = w2−n. Proof. Consider the equations 3x1 + 2x2 + 1(n− (x1 + x2)) = w1 3y1 + 2y + 2 + 1(n− (y1 + y2)) = w2 3(n− (x1 + y1)) + 2(n− (x2 + y2)) + 1(n− (2n− (x1 + x2 + y1 + y2))) = w3 Let the above three equations be called as (A). Firstly we claim that under the given conditions (1),(2),(3) and (4) we can find non negative integers x1,x2,y1,y2 satisfying equations (A) such that n−(xl + x2) ≥ 0, n−(y1 + y2) ≥ 0, n−(xl + y1) ≥ 0, n− (x2 + y2) ≥ 0, n− [2n− (xl + x2 + y1 + y2)] ≥ 0. Let these five inequalities be called as (B). The equations in (A) can be simplified as 2x1 + x2 = w1 −n (2.1.1) 2y1 + y2 = w2 −n (2.1.2) 2x1 + 2y1 + x2 + y2 = 4n−w3 (2.1.3) 47 Reji T, Ruby R Since n = w1+w2+w3 6 , w1 −n + w2 −n = 4n−w3. Thus to prove our claim we have to solve the equations ( 2.1.1), ( 2.1.2) such that all the inequalities in (B) are satisfied. Observing ( 2.1.1) and ( 2.1.2), it is clear that they have a positive integral solution such that all the inequalities in (B) are satisfied if and only if w1 − n ≤ 2n and w2 − n ≤ 2n. By condition (2), these inequalities holds. Let m = w1 −n, l = w2 −n. Case 1: w2 −n ≤ n Here we have to solve the equations 2x1 + x2 = m, 2y1 + y2 = l. Subcase 1.1: m is even Take x1 = m 2 , x2 = 0, y1 = 0, y2 = l. Thus x1 +x2 = m 2 ≤ n, y1 +y2 = l ≤ n, xl + y1 = m 2 ≤ n, x2 + y2 = l ≤ n. So the only inequality in (B), which has to be verified is n− (2n− (xl + x2 + y1 + y2)) ≥ 0. Since n− (xl + x2) ≥ 0 and n−(y1 +y2) ≥ 0, xl +x2 +y1 +y2 ≤ 2n. Thus n−(2n−(xl +x2 +y1 +y2)) ≥ 0 ⇔xl + x2 + y1 + y2 ≥ n⇔ m2 + l ≥ n⇔ w1−n 2 + w2 −n ≥ n⇔w1 + 2w2 ≥ 5n ⇔ w1 + 2w2 ≥ 5( w1+w2+w36 ) ⇔ 5w3 ≤ w1 + 7w2, which is always true, since w1 ≥ w2 ≥ w3· Thus in this subcase all the inequalities in (B) are satisfied. Subcase 1.2: m is odd Take x1 = m−1 2 , x2 = 1, y1 = 1, y2 = l − 2. Here x1 + y1 = m−12 + 1 ≤ n [since m is odd and m ≤ 2n]. x2 + y2 = 1 + l − 2 = l − 1 ≤ n [since in this subcase l = w2−n ≤ n], y1 + y2 = l−1 ≤ n and x1 + x2 = m−12 + 1 ≤ n. As in the above subcase n− (2n− (x1 + x2 + y1 + y2)) ≥ 0 ⇔x1 + x2 + y1 + y2 ≥ n ⇔ m − 1 + 2l ≥ 2n ⇔ w1 + 2w2 − 1 ≥ 5n ⇔ 5w3 + 6 ≤ w1 + 7w2. Since w3 ≥ 2,w1 > 2 + n, w2 ≥ 2 + n, we get w1 ≥ 3, w2 ≥ 3, w3 ≥ 2. Also w1 ≥ w2 ≥ w3. Thus 7w2 ≥ 5w3 + 2w3 ≥ 5w3 + 4. Thus w1 + 7w2 ≥ 5w3 + 4 + w1 ≥ 5w3 + 7 > 5w3 + 6. Hence x1 + x2 + y1 + y2 ≥ n and thus n− (2n− (x1 + x2 + y1 + y2)) ≥ 0. Thus in this subcase also all the conditions in (B) are satisfied. Case 2: w2 −n > n Here also we have to solve the equations 2x1 + x2 = m, 2y1 + y2 = l. Subcase 2.1: m is even and l− m 2 is even Take x1 = m 2 , x2 = 0, y1 = l− m 2 2 , y2 = m 2 . Here n− (xl + x2) = n− m2 ≥ 0, since m 2 ≤ n. n−(y1 +y2) = n−( 2l−m4 + m 2 ) = n− 2l+m 4 . Thus n−(y1 +y2) ≥ 0 ⇔ 2l+m 4 ≤ n ⇔ 2(w2 −n) + w1 −n ≤ 4n ⇔ 5w2 ≤ w1 + 7w3, which is true by the given condition (3). Similarly n−(x1 + y1) ≥ 0 and n−(x2 + y2) ≥ 0. As in the above case, n− (2n− (x1 + x2 + y1 + y2)) ≥ 0 ⇔x1 + x2 + y1 + y2 ≥ n⇔ m 2 + 2l−m 4 + m 2 ≥ n ⇔ 3m + 2l ≥ 4n ⇔ 3w1 + 2w2 ≥ 9n ⇔ 3w3 ≤ 3w1 + w2, which is always true since w1 ≥ w2 ≥ w3. Subcase 2.2: m is even and l− m 2 is odd Here take x1 = m 2 , x2 = 0, y1 = l− m 2 +1 2 , y2 = m 2 − 1. We can easily verify that n− (xl + x2) ≥ 0 ⇔ 5w2 ≤ w1 + 7w3 − 12, which is true by condition (3). 48 On decomposition of multistars into multistars Similarly n − (y1 + y2) ≥ 0. Also it easily follows that n − (x1 + y1) ≥ 0 and n− (x2 + y2) ≥ 0. n− (2n− (x1 + x2 + y1 + y2)) ≥ 0 ⇔ 3w1 + w2 ≥ 3w3 + 4. But w1 ≥ w2 ≥ w3 ≥ 2 and by condition (2), w1 ≥ n + 2 and n = w1+w2+w36 . Thus w1 ≥ 4. Also 3w1 + w2 = w1 + 2w1 + w2 ≥ w1 + 3w3 ≥ 3w3 + 4 (since w1 ≥ 4). Thus n− (2n− (x1 + x2 + y1 + y2)) ≥ 0 and hence all the inequalities in (B) are satisfied. Subcase 2.3: m is odd and l− m−1 2 is even Take x1 = m−1 2 , x2 = 1, y1 = l− m−1 2 2 , y2 = m−1 2 . n−(x1 + x2) = n−( m−12 + 1) ≥ 0 ⇔ 1 + m−1 2 ≤ n. This is true since m ≤ 2n and m is odd. Similarly n−(x2 + y2) ≥ 0. Also n−(x1 + y1) ≥ 0 ⇔ 5w2 ≤ w1 + 7w3 + 6, which is true by condition (3). Similarly n−(y1+y2) ≥ 0. Also n−(2n−(x1+x2+y1+y2)) ≥ 0 ⇔ 3w1 + w2 + 2 ≥ 3w3, which is always true since w1 ≥ w2 ≥ w3. Thus all the inequalities in (B) are satisfied. Subcase 2.4: m is odd and l− m−1 2 is odd Take x1 = m−1 2 , x2 = 1, y1 = l− m+1 2 2 , y2 = m+1 2 . n− (xl + x2) = n− m−12 + 1) = n − m+1 2 . Since m is odd and m ≤ 2n, m+1 2 ≤ n. So n − (xl + x2) ≥ 0. n − (x2 + y2) = n − ( m+12 + 1) ≥ 0 ⇔ w1 ≤ w2 + w3 − 6, which is true by condition(4). Also we can verify that n−(xl + y1) ≥ 0 and n−(y1 + y2) ≥ 0 by condition(3). Similarly n−(2n−(xl +x2 +y1 +y2)) ≥ 0 ⇔ 3w1 +w2 + 6 ≥ 3w3, which is always true. Hence all the conditions in (B) are satisfied in this subcase also. Hence our claim is proved in both cases. Thus using equations (A), we can properly partition w1 into x1 copies of 3, x2 copies of 2 and n− (x1 + x2) copies of 1’s. w2 can be partitioned into y1copies of 3, y2 copies of 2 and n− (y1 + y2) copies of 1. w3 can be partitioned into n − (x1 + y1) copies of 3, n − (x2 + y2) copies of 2 and n−(2n−(x1 + x2 + y1 + y2)) copies of 1. Using these partitions of w1,w2,w3, we can decompose Sw1,w2,w3 into copies of S1,2,3.2 2.2 K1,m decomposability of Sw1,w2,··· ,wn Theorem 2.2. The multistar Sw1,w2,··· ,wn , w1 ≥ w2 ≥ ··· ≥ wn, is K1,m- decomposable (n ≥ m) if and only if 1. Σni=1wi ≡ 0(mod m) 2. For each k = 1, 2, · · · ,m− 1, Σki=1wi ≤ k m−k (wk+1 + · · · + wn) Proof. Suppose the multistar the multistar Sw1,w2,··· ,wn , w1 ≥ w2 ≥ ···≥ wn, is K1,m-decomposable (n ≥ m). Then clealy Σni=1wi ≡ 0(mod m). To prove (2), assume the contrary. Suppose that ∑k i=1 wi > k m−k (wk+1 +· · ·+ 49 Reji T, Ruby R wn), for some k with 1 ≤ k ≤ m− 1. This implies (m−k) k∑ i=1 wi > k(wk+1 + · · · + wn) ⇒ m k∑ i=1 wi > k n∑ i=1 wi ⇒ k∑ i=1 wi > k m ( n∑ i=1 wi). This is not possible, since 1 m ( ∑n i=1 wi) is the number of copies of K1,m to which Sw1,w2,··· ,wn can be decomposed. Each copy of K1,m can contribute at most k to ∑k i=1 wi. Thus ∑k i=1 wi ≤ k m ( ∑n i=1 wi). We prove sufficiency by induction on w = ∑n i=1 wi. For w = m, the multistar is K1,m itself. If w ≥ 2m, one copy of K1,m is deleted from sw1,w2,··· ,wm by sub- tracting m number of 1’s from the largest m multiplicities. The multistar obtained after this process still satisfies conditions 1 and 2. Hence by induction the proof follows.2 2.3 S2 m decomposability of Sw1,w2,··· ,wn Theorem 2.3. The multistar Sw1,w2,··· ,wn , w1 ≥ w2 ≥ ···≥ wn, is S2 m -decomposable (n ≥ m) if and only if 1. Σni=1wi ≡ 0(mod 2m) 2. For 1 ≤ i ≤ n, wi ≡ 0(mod 2) 3. For each k = 1, 2, · · · ,m− 1, Σki=1wi ≤ k m−k (wk+1 + · · · + wn) Proof. Assume that the multistar Sw1,w2,··· ,wm is S2 m -decomposable. Then as in the above theorems conditions 1 and 3 hold. Since Sw1,w2,··· ,wm is S2 m - decomposable, clearly wi ≡ 0(mod 2). We prove sufficiency by induction on w = ∑n i=1 wi. For w = 2m, the mul- tistar is S2 m itself. If w ≥ 4m, delete one copy of S2m from Sw1,w2,··· ,wn by subtracting m number of 2’s from the largest m multiplicities. The multistar ob- tained after this deletion still satisfies all the three conditions. Hence by induction the proof follows.2 The above two theorems can be generalized to characterize Sm l -decomposable multistars. 2.4 Sm l decomposability of Sw1,w2,··· ,wn Theorem 2.4. The multistar Sw1,w2,··· ,wn , w1 ≥ w2 ≥ ···≥ wn, is Sm l -decomposable (n ≥ l) if and only if 50 On decomposition of multistars into multistars 1. Σni=1wi ≡ 0(mod lm) 2. For 1 ≤ i ≤ n, wi ≡ 0(mod m) 3. For each k = 1, 2, · · · , l− 1, Σki=1wi ≤ k l−k (wk+1 + · · · + wn) Proof. Assume that the multistar Sw1,w2,··· ,wn is Sm m -decomposable. Then conditions 1,2 and 3 follows as in the above theorem. The sufficiency can similarly be proved using induction by deleting one copy of Sm m from Sw1,w2,··· ,wn by subtracting l number of m’s from the largest l multiplicities.2 3 Conclusions In this paper we have characterized those multistars which are S1,2,3-decomposable, K1,m-decomposable, S2 m -decomposable and Sm l -decomposable. 4 Acknowledgement We are indebted to Prof.M.I.Jinnah, formerly University of Kerala, for his guidance and valuable suggestions during the preparation of this manuscript. References A Bialostocki and Y Roditty. 3k 2-decomposition of a graph. Acta Mathematica Academiae Scientiarum Hungarica, 40(3-4):201–208, 1982. Darryn E Bryant, Saad El-Zanati, Charles Vanden Eynden, and Dean G Hoffman. Star decompositions of cubes. Graphs and Combinatorics, 17(1):55–59, 2001. Hung-Chih Lee and Chiang Lin. Balanced star decompositions of regular multi- graphs and λ-fold complete bipartite graphs. Discrete mathematics, 301(2-3): 195–206, 2005. Hung Chih Lee, Jeng Jong Lin, Chiang Lin, and Tay Woei Shyu. Multistar de- composition of complete multigraphs. Ars Combinatoria, 74:49–63, 2005. Chiang Lin and Tay-Woei Shyu. A necessary and sufficient condition for the star decomposition of complete graphs. Journal of Graph Theory, 23(4):361–364, 1996. Jenq-Jong Lin. Decomposition of balanced complete bipartite multigraphs into multistars. Discrete mathematics, 310(5):1059–1065, 2010. 51 Reji T, Ruby R Miri Priesler and Michael Tarsi. On some multigraph decomposition problems and their computational complexity. Discrete Mathematics, 281(1-3):247–254, 2004. Miri Priesler and Michael Tarsi. Multigraph decomposition into stars and into multistars. Discrete mathematics, 296(2-3):235–244, 2005. Tay-Woei Shyu. Decomposition of complete bipartite graphs into paths and stars with same number of edges. Discrete Mathematics, 313(7):865–871, 2013. 52