Ratio Mathematica Volume 44, 2022 Split Domination Decomposition of Path Graphs E. Ebin RajaMerly1 Praisy B2 Abstract A decomposition (G1, G2, G3, …, Gn) of G is said to be a split domination decomposition (SDD), if the following conditions are satisfied:(i) each Gi is connected(ii)γs(Gi) = i, 1≤ i ≤ n. In this paper, we prove that path, path corona and subdivision of path graph admit SDD. Keywords: split domination, decomposition, split domination decomposition. 2010 AMS subject classification: 05C12, 05C693 1Associate professor, Research Department of Mathematics, Nesamony Memorial Christian College, Marthandam. Tamilnadu, India. Mail Id: ebinmerly@gmail.com 2Research Scholar, Research Department of Mathematics, Nesamony Memorial Christian College, Marthandam, Tamilnadu, India. Mail. Id: praisyblessed@gmail.com 3Received on June 28th, 2022. Accepted on Aug 10th, 2022. Published on Nov30th, 2022.doi: 10.23755/rm.v44i0.904. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors.This paper is published under the CC-BY license agreement. 175 E. Ebin Raja Merly and Praisy B 1. Introduction Graph theory in mathematics refers to the study of graphs. The theory of domination is one of the rapidly developing areas in graph theory. The concept of split domination was developed by Veerabhadrappa R. Kulli and Bidarahalli Janakiram [2]. Another important concept in graph theory is decomposition of graphs. Decompositions are imposed by applying several conditions on Gi in the decompositions by several authors based on their studies. We introduce a new concept split domination decomposition of a graph which is motivated by the concepts of Linear path decomposition [3] and Connected Domination Decomposition [4]. We have considered here simple undirected graphs without loops or multiple edges. The order and size of the graph are indicated by p and q respectively. Terms not defined here are used in the sense of Frank Harary [1]. 2. Preliminaries Definition2.1: A dominating set D of a graph G = (V, E) is a set of vertices such that each vertex of G is either in D or has at least one neighbor in D. Definition 2.2: A dominating set D of a graph G = (V, E) is a split dominating set if the induced sub graph is disconnected. The split domination number γs(G ) of G is the minimum cardinality of a split dominating set. Definition2.3: If G1, G2, G3, …, Gn are edge disjoint sub graphs of G such that E(G) = E (G1) E (G2) … E (Gn), then (G1, G2, G3,…, Gn) is said to be decomposition of G. Definition2.4: The corona Pp ⊙ K1 is the graph constructed from a copy of Pp, where for each vertexu ∈ V(Pp), a new vertex u ′and a pendent edge uu′ are added. It is denoted by Pp + and is called comb. Definition 2.5: A subdivision of a graph G is a graph obtained by inserting a new vertex in each edge of G and is denoted by S(G). 3. Split Domination Decomposition Definition 3.1: A Decomposition (G1, G2, G3, …, Gn) of G is said to be a split domination decomposition (SDD), if the following conditions are satisfied: (i). each Gi is connected (ii). 𝛾𝑠(𝐺𝑖 ) = 𝑖, 1≤ 𝑖 ≤ 𝑛. 176 Split Domination Decomposition of Path Graphs Example 3.2: G G1 G2 Figure 1: Graph G and its SDD (G1, G2) Remark 3.3: A path with 3 vertices have split domination number 1 and path having 3k-2,3k-1 and 3k vertices have the split domination number k, k. 2. Theorem 3.4: A pathP𝑝, 3n2−3n+6 2 ≤ p ≤ 3n2+n+2 2 admits split domination decomposition (G1, G2, G3, …, Gn) if and only if∑ γs(Gi) = n i=1 𝑛(𝑛+1) 2 . Proof: Let Pp=u1u2 … up be a path of order p. Assume that Pp , 3n2−3n+6 2 ≤ p ≤ 3n2+n+2 2 admits split domination decomposition (G1, G2, G3,…, Gn). Clearly γs(Gi) = i , 1 ≤ i ≤ n. Therefore γs(G1) + γs(G2) + ⋯ + γs(Gn) = 1 + 2 + ⋯ + n ∑ γs(Gi) = n i=1 n(n + 1) 2 Conversely, assume that ∑ γs(Gi) = n i=1 n(n+1) 2 . Clearly γs(Gi) = i , 1≤ i ≤ n. Therefore Pp admits split domination decomposition (G1, G2, G3, …,Gn). Next, we have to find the bound for p. By remark 3.3, the subgraphs G1, G2, G3, …, Gnof Pp having minimum possible vertices are G1 = u1u2u3 G2 = u3u4u5u6 G3 = u6u7u8u9u10u11u12 ⁞ Gn = umum+1 … up Wherem = 3n2−9n+12 2 , p = 3n2−3n+6 2 Clearly |V(Pp)| = |V(G1)| + |V(G2)| + ⋯ + |V(Gn)| u5 u2 𝑢1 u3 u4 u1 u1 u2 u3 u5 u3 u4 u1 177 E. Ebin Raja Merly and Praisy B p =(3+4+… +3𝑛 − 2) − (𝑛 − 1)= 3n2−3n+6 2 Next, the maximum possible vertices of subgraphsG1, G2, G3,…,Gn of P𝑝 are G1 = u1u2u3 G2 = u3u4u5u6u7u8 G3 = u8u9u10u11u12u13u14u15u16 ⁞ Gn = umum+1 … up Wherem = 3n2−5n+4 2 , p = 3n2+n+2 2 Clearly |V(Pp)| = |V(G1)| + |V(G2)| + ⋯ + |V(Gn)| p = (3+6+… +3n) − (n − 1) = 3n2+n+2 2 Therefore 3n2−3n+6 2 ≤ p ≤ 3n2+n+2 2 . Corollary 3.5: If 3n2+n+2 2 < 𝑝 < 3n2+3n+6 2 , then Ppdoes not admit split domination decomposition. Theorem 3.6:Pp + admits split domination decomposition (G1, G2, G3, …, Gn) if and only if Pp has n2+n 2 (n > 1)vertices. Proof: Let Pp=u1u2 … up be a path with p vertices. If we join the verticesu1 ′ , u2 ′ , … , up ′ to u1, u2, … , up respectively, then we get Pp +. Assume that Pp has n2+n 2 (n > 1)vertices. To prove Pp + admits split domination decomposition (G1, G2, G3,…,Gn). Suppose p = n2+n 2 G1 =< {𝑢1, u2, u1 ′ } > G2 =< {u2, u3, u2 ′ , u3 ′ } > G3=< {𝑢3, u4, u5, u6, u4 ′ , u5 ′ , u6 ′ } > ⁞ Gn =< {𝑢l, ul+1, … , up, ul+1 ′ , … , up ′ } > Notice that the minimum split dominating set of Gn has vertices and Pp has 1+2+3+…. + = n(n+1) 2 = n2+n 2 vertices. Clearly γs(Gi) = i , 1 ≤ i ≤ n. Therefore (G1, G2, G3, . . . ,Gn)is a split domination decomposition of Pp +. Conversely, suppose Pp + admits split domination decomposition. To prove Pp has n2+n 2 , (n > 1)vertices. Suppose not, Case (i):|V(Pp)| > n2+n 2 We join m vertices in Pp where m=1, 2, 3, …, or n. Constructing (G1, G2, G3…, Gn) in the above, we have remaining m vertices where m=1, 2, 3, …, or n. We cannot arrange 178 Split Domination Decomposition of Path Graphs the m vertices in the minimum split dominating set of Gi otherwise (G1, G2, G3, …, Gn) would not be a split domination decomposition for Pp +. If these m vertices alone to give a sub graph Gkm , then (G1,G2, …,Gn , Gkm ) would not be a split domination decomposition for Pp +which is a contradiction. Case (ii):|𝑉(Pp)| < n2+n 2 . We eliminate m vertices in Pp where =1, 2, 3, … or n − 1.Constructing(G1, G2, G3, …, Gn) in the above, we have remaining m vertices where 𝑚 = 𝑛 − 1, n-2, .., or n-(n-1). We cannot arrange the m vertices in the minimum split dominating set of Gi otherwise (G1, G2, G3,…, Gn) would not be a split domination decomposition for Pp +. If these m vertices alone to give a sub graph Gkm , then(G1,G2 ,…,Gn−1 , Gkm ) would not be a split domination decomposition for Pp +which is a contradiction. Therefore Pp has n2+n 2 , (n > 1)vertices. Note 3.7: In general, if Pp admits split domination decomposition, then S (Pp) need not admit split domination decomposition and vice-versa. So we cannot use the range of p as in theorem 3.4 to S (𝑃𝑝). Theorem 3.8: Let Pp be a (p, q) -path. Subdivision of the path graph S (Pp) admits split domination decomposition (G1, G2, G3,…,Gn)if and only if 2n2−6n+14 2 ≤ p ≤ n2+5n−8 2 . Proof: Let Pp=u1u2 … up be a path with p vertices. Then S (Pp) has 2p − 1vertices. Assume that S (Pp) admits split domination decomposition. Now we can find the range of p if and only if S (Pp) admits split domination decomposition. From note 3.7, we can’t apply the range of 𝑝 in Ppas in theorem 3.4 toS (Pp). Hence using the range of p in Pp to S (Pp), the following table shows the probabilities for S (Pp) admits split domination decomposition. Table:1 No. of decompositions (𝑛) 2 3 4 5 6 7 No. of vertices in𝑃𝑝(𝑝) 4 7 8 11 12 13 14 17 18 19 20 21 25 26 27 28 29 34 35 36 37 38 39 No. of vertices in 𝑆( 𝑃𝑝) 7 13 15 21 23 25 27 33 35 37 39 41 49 51 53 55 57 67 69 71 73 75 77 179 E. Ebin Raja Merly and Praisy B Using Newton’s forward difference formula, we have to find the upper and lower bound of p for Pp such that S (𝑃𝑝) admitssplit domination decomposition. To find the lower bound of p, using table-1. By Newton’s forward formula,p = p0+ u 1! ∆p0+ u(u−1) 2! ∆2p0 + ⋯ Where u= n−𝑛0 ℎ = n − 3 ( n0 = 3 andh = 1) Here p0 = 7, ∆p0 = 4, ∆ 2p0 = 2 , ∆ 3p0 = 0 Therefore = 2n2−6n+14 2 Next, to find the upper bound of p, using table-1. By Newton’s forward formula, = p0+ u 1! ∆p0+ u(u−1) 2! ∆2p0 + ⋯ Where u = n−𝑛0 ℎ = n − 3 ( n0 = 3 and h = 1) Here p0 = 8, ∆p0 = 6, ∆ 2p0 = 1 , ∆ 3p0 = 0 Therefore = n2+5n−8 2 Therefore S(Pp) admits split domination decomposition, if 2n2−6n+14 2 ≤ p ≤ n2+5n−8 2 . Conversely, Assume that 2n2−6n+14 2 ≤ p ≤ n2+5n−8 2 . To prove S (Pp) admit split domination decomposition. Suppose not, Consider the lower bound of p, if we eliminate one vertex fromPp,then the corresponding S(Pp) will not admit split domination decomposition. Hence p = 2n2−6n+14 2 − 1 < 2n2−6n+14 2 .which is a contradiction. Consider the upper bound of p, if we join one vertex to Pp, then the corresponding S (Pp) will not admit split domination decomposition. Hencep= n2+5n−8 2 +1> n2+5n−8 2 .which is a contradiction. Therefore S (Pp) admits split domination decomposition. 4. Conclusion In this paper, we deal that path, path corona and subdivision of path graph admits split domination decomposition. Further investigations could also be done to get the condition at which some graphs admit split domination decomposition. 180 Split Domination Decomposition of Path Graphs References [1] Harary F, “Graph Theory”, Narosa Publishing House, New Delhi (1998) [2] Kulli, V. R and Janakiram, B., “The split domination number of a graph”, Graph Theory Notes of New York, XXXII,16-19(1997). [3] E. Ebin Raja Merly and N. Gnanadhas, (2011), “Linear Path decomposition of Lobster”, International Journal of Mathematics Research. Volume 3, Number 5. 447- 455. [4] Jeya Jothi D, E. Ebin Raja Merly, “Connected Domination Decomposition of Helm Graph”, International Journal of Scientific Research and Review.Vol.7, Issue10,2018. [5] Sr Little Femilin Jana. D., Jaya. R., Arokia Ranjithkumar, M., Krishnakumar. S., “Resolving Sets and Dimension in Special Graphs”, Advances And Applications In Mathematical Sciences 21 (7) (2022), 3709 – 3717. 181 https://scholar.google.com/citations?view_op=view_citation&hl=en&user=xWCP70YAAAAJ&sortby=pubdate&authuser=1&citation_for_view=xWCP70YAAAAJ:IjCSPb-OGe4C