Ratio Mathematica Volume 45, 2023 Strong perfect cobondage number of standard graphs Govindalakshmi T.S.1 Meena N.2 Abstract Let G be a simple graph. A subset S  V(G) is called a strong (weak) perfect dominating set of G if |Ns(u) ∩ S| = 1(|Nw(u) ∩ S| = 1) for every u ∊V(G) - S where Ns(u) = {v ∊ V(G) / uv ∈ 𝐸(𝐺), deg v ≥ deg u} (Nw(u) = {v ∊V(G) / uv ∈ 𝐸(𝐺), deg v ≤ deg u}. The minimum cardinality of a strong (weak) perfect dominating set of G is called the strong (weak) perfect domination number of G and is denoted by γsp(G)(γwp(G)). The strong perfect cobondage number bcsp(G) of a nonempty graph G is defined to be the minimum cardinality among all subsets of edges X ⊆ E(G) for which 𝛾sp (G + X) < 𝛾sp(G). If bcsp(G) does not exist, then bcsp(G) is defined as zero. In this paper study of strong perfect cobondage number of standard graphs and some special graphs are determined. Keywords: Strong perfect dominating set, strong perfect domination number and strong perfect cobondage number. AMS subject classification: 05C693 1Research Scholar, Reg. No. 12566, P.G. & Research Department of Mathematics, The M.D.T. Hindu College, Tirunelveli –10 & Assistant Professor of Mathematics, Manonmaniam Sundaranar University College, Puliangudi-627855. Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli -627 012, TamilNadu, India. Email: laxmigopal2005@gmail.com 2Assistant Professor, P.G. & Research Department of Mathematics, The M.D.T. Hindu College, Tirunelveli-10. Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli-627 012, Tamil Nadu, India. Email: meena@mdthinducollege.org. 3 Received on July 21th, 2022. Accepted on October 15th, 2022. Published on January 30, 2023. doi: 10.23755/rm.v45i0.983. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published under the CC-BY license agreement 66 Govindalakshmi T S and Meena N 1. Introduction Let G be a simple graph with vertex set V(G) and edge set E(G). A dominating set D of G is a subset of V(G) such that every vertex in V – D is adjacent to at least one vertex in D [6]. A set D  V(G) is a strong(weak) dominating set of G [5] if every vertex in V – D is strongly(weakly) dominated by at least one vertex in D. The strong (weak) domination number γs(G) (γw(G)) is the minimum cardinality of a strong (weak) dominating set of G. A dominating set S is a perfect dominating set of G [1] if |N(v) ∩S| = 1 for each v ∊ V – S. Motivated by these definitions, the authors defined strong perfect domination in graphs [2]. In [4], V.R. Kulli and B. Janakiram introduced the concept of cobondage number of a graph. The cobondage number of graph G is the minimum cardinality among the set of edges X such that 𝛾(G+X) < 𝛾(G). In this paper strong perfect cobondage number is defined and strong perfect cobondage number of paths, cycle, bistar, complete bipartite graph and some special graphs are determined. For all graph theoretic terminologies and notations Harary [3] is followed. 2. Preliminaries Definition 2.1. [2] Let G be a simple graph. A subset S  V(G) is called a strong (weak) perfect dominating set of G if |Ns(u) ∩ S| = 1(|Nw(u) ∩ S| = 1) for every u ∊V(G) - S where Ns(u) = {v ∊ V(G)/uv ∈ 𝐸(𝐺), deg v ≥ deg u} (Nw(u) = {v ∊V(G)/uv ∈ 𝐸(𝐺), deg v ≤ deg u}. Remark 2.2. [2] The minimum cardinality of a strong (weak) perfect dominating set of G is called the strong (weak) perfect domination number of G and is denoted by γsp(G)(γwp(G)). Definition 2.3. Bi star is the graph obtained by joining the apex vertices of two copies of star K1, n. Definition 2.4. The wheel Wn is defined to be the graph Cn - 1 + K1, n ≥ 4. Definition 2.5. The helm Hn is the graph obtained from the wheel Wn with n spokes by adding n pendant edges at each vertex on the wheel’s rim. Definition 2.6. The corona G1⨀ G2 of two graphs G1 and G2 (where Gi has pi points and qi lines) is defined as the graph G obtained by taking one copy of G1 and p1 copies of G2, and then joining the ith point of G1 to every point in the i th copy of G2. Definition 2.7. The lily graph Ln, n ≥ 2 can be constructed by two-star graphs 2K1, n, n ≥ 2 joining two path graphs 2Pn, n ≥ 2 with sharing a common vertex. Theorem 2.8. [2] For any path Pm, 67 Strong perfect cobondage number of standard graphs Then 𝛾sp (Pm) = { 𝑛 𝑖𝑓 𝑚 = 3𝑛, 𝑛𝜖𝑁 𝑛 + 1 𝑖𝑓 𝑚 = 3𝑛 + 1, 𝑛𝜖𝑁 𝑛 + 2 𝑖𝑓 𝑚 = 3𝑛 + 2, 𝑛 𝜖𝑁 Theorem 2.9 [2] For any cycle Cm, Then 𝛾sp (Cm) = { 𝑛 𝑖𝑓 𝑚 = 3𝑛, 𝑛𝜖𝑁 𝑛 + 1 𝑖𝑓 𝑚 = 3𝑛 + 1, 𝑛𝜖𝑁 𝑛 + 2 𝑖𝑓 𝑚 = 3𝑛 + 2, 𝑛 𝜖𝑁 Theorem 2.10. [2] Let G be a connected graph with |V(G)| = n. Then 𝛾sp (G ⨀K1) = n. Remark 2.11. [2] (i) 𝛾sp (D r, s) = 2, r, s 𝜖 N (ii) 𝛾sp (Km, n) = { 2 𝑖𝑓 𝑚 = 𝑛, 𝑚, 𝑛 ≥ 2 𝑚 + 𝑛 𝑖𝑓 𝑚 ≠ 𝑛 , 𝑚, 𝑛 ≥ 2 (iii) 𝛾sp (Hn) = n, 𝑛 ≥ 5 𝑎𝑛𝑑 𝛾sp (H4) = 3. 3. Main Results Definition 3.1. The strong perfect cobondage number bcsp(G) of a graph is defined to be the minimum cardinality among all subsets of edges X ⊆ E(G) for which 𝛾sp (G + X)< 𝛾sp(G). If bcsp(G) does not exist, then bcsp(G) is defined as zero. Example 3.2. Consider the graphs G and G + e in the following figures 1 and 2 respectively. Fig. 1. Fig. 2. 68 Govindalakshmi T S and Meena N {v3, v7, v6}, {v3, v7, v5, v4} and {v3, v8, v9, v4, v5} are some strong perfect dominating sets of G. Hence 𝛾sp(G) ≤ 3. Since there is no full degree vertex in G, 𝛾sp(G) ≥ 2. There are five pendent vertices. Any strong perfect dominating sets contains either pendent vertices or their support vertices. v3, v7, v5 are the support vertices adjacent with pendent vertices. Therefore 𝛾sp(G) ≥ 3. Hence 𝛾sp(G) = 3. Let e = v6v7. {v3, v7}, {v7, v4, v1, v2} are some strong perfect dominating sets of G + e. Therefore 𝛾sp(G + e)≤ 2. Since there is no full degree vertex in G + e, 𝛾sp(G) ≥ 2. Hence 𝛾sp(G + e) = 2< 𝛾sp(G). Hence bcsp(G) = 1. Theorem 3.3. bcsp (Pm) = { 1 𝑖𝑓 𝑚 = 3𝑛 + 1, 𝑛 ≥ 1 1𝑖𝑓 𝑚 = 3𝑛 + 2, 𝑛 ≥ 1 3 𝑖𝑓 𝑚 = 3𝑛, 𝑛 ≥ 2 Proof. Let G = Pm, m ≥ 4. Let V(G) = {vi / 1≤i≤m}. Case (1). Let m = 3n+1, n ≥ 1. 𝛾sp(G) = n+1. Let e = v3n – 1v3n+1, deg v3n-1= △ (𝐺 + 𝑒) = 3. T = {v2, v5, v8, …, v3n -1} is a strong perfect dominating set of G + e. |T| = n. Therefore 𝛾sp (G + e) ≤ n. Let S be any strong perfect dominating set of G + e. Since v3n – 1 is the unique maximum degree vertex in G + e, v3n – 1 belongs to S. The subgraph induced by the vertices v1, v2, …, v3n – 2 is P3n – 3. Therefore 𝛾sp (P3n - 3) = n – 1. |S| = n. Hence 𝛾sp(G + e) ≥ n. Therefore 𝛾sp (G + e) = n < n+1 = 𝛾sp(G). Hence bcsp(G) = 1. Case (2). Let m = 3n+2, n ≥ 1. 𝛾sp(G) = n+2. Let e = v3n v3n+2, deg v3n = △(G + e) = 3. T1 = {v1, v3, v6, …, v3n}, T2 = {v2, v5, …, v3n - 4 v3n-3, v3n} are some strong perfect dominating sets of G + e. |T1| = |T2 | = n + 1. Therefore 𝛾sp (G + e) ≤ n+1. Let S be any strong perfect dominating set of G +e. v3n is strongly dominates v3n + 2. Therefore v3n 𝜖 S. The subgraph induced by the vertices v1, v2, …, v3n – 2 is P3n – 2. Therefore 𝛾sp(P3n - 2) = 𝛾sp(P3(n – 1) + 1) = n. Therefore |S| = n + 1. 𝛾sp (G + e) ≥ n+1. Therefore 𝛾sp (G + e) = n+1 < n+2 = 𝛾sp(G). Hence bcsp(G) = 1. Case (3). Let G = P3n, n ≥ 2. 𝛾sp(G) = n. When one or two edges added with P3n strong perfect domination number of the resulting graph either increases or remains same. Hence bcsp(G) ≥ 3. Let e1 = v1v3, e2 = v3v5, e3 = v3v6. Let X = {e1, e2, e3}. T = {v3, v8, v11, …, v3n-1}is a strong perfect dominating set of G+X. |T| = n – 1. Therefore 𝛾sp (G+X) ≤ n - 1. Let S be any strong perfect dominating set of G + X. deg v3 = 5. v3 is the unique maximum degree vertex of G + X. v3 belongs to S. The subgraph induced by the vertices v7, v8, …, v3n is a P3n – 6. Therefore 𝛾sp(P3n - 6) = n - 2. Therefore |S| = n – 2 + 1 = n - 1. 𝛾sp (G + X) ≥ n - 1. Therefore 𝛾sp (G + X) = n - 1 < n = 𝛾sp(G). Hence bcsp(G) = 3. Remark. Let m = 3. 𝛾sp(G) = 1. Hence bcsp(G) = 0. Theorem 3.4. bcsp (Cm) = { 1 𝑖𝑓 𝑚 = 3𝑛 + 1, 𝑛 ≥ 1 1 𝑖𝑓 𝑚 = 3𝑛 + 2, 𝑛 ≥ 1 3 𝑖𝑓 𝑚 = 3𝑛, 𝑛 ≥ 2 Proof. Let G = Cm, m ≥ 4. Let V(G) = {vi / 1 ≤ 𝑖 ≤ m}. Case (1). Let m = 3n+1, n ≥ 1. 𝛾sp(G) = n+1. Let e = v1v3. T= {v1, v5, v8, …, v3n-1} is a strong perfect dominating set of G + e. |T| = n. Therefore 𝛾sp (G +e) ≤ n. Let S be any strong perfect dominating set of G + e. Since v1, v3 are maximum degree vertices in 69 Strong perfect cobondage number of standard graphs G+ e, either v1 belongs to S or v3 belongs to S. Suppose v1 belongs to S (Proof is similar if v3 belongs to S). The subgraph induced by the vertices v4, v5, …, v3n is the path P3n – 3. 𝛾sp(P3n - 3) = n - 1. Hence 𝛾sp (G + e) ≥ n. Therefore 𝛾sp (G + e) = n < n+1 = 𝛾sp(G). Hence bcsp(G) = 1. Case (2). Let m = 3n+2, n ≥ 2. 𝛾sp(G) = n+2. Let e = v1v3n + 1. T = {v1, v4, v7, …, v3n-2, v3n - 1} is a strong perfect dominating set of G + e. |T| = n+1. Therefore 𝛾sp (G + e) ≤ n+1. Let S be any strong perfect dominating set of G + e. Since v1, v3n + 1 are maximum degree vertices in G + e, either v1 belongs to S or v3n + 1 belongs to S. Suppose v1 belongs to S (Proof is similar if v3n + 1 belongs to S). The subgraph induced by the vertices v3, v4, …, v3n is the path P3n – 2. Therefore 𝛾sp(P3n - 2) = 𝛾sp (P3(n – 1) +1) = n. Hence𝛾sp (G + e) ≥ n+1. Therefore 𝛾sp (G + e) = n+1 < n+2 = 𝛾sp(G). Hence bcsp(G) = 1. Subcase (2a). If n = 1, 𝛾sp(C5) = 3. Let e = v1v4. {v1, v2} is the unique 𝛾sp - set of G + e. 𝛾sp (G + e) = 2 < 𝛾sp(G). Hence bcsp(C5) = 1. Case (3). Let m = 3n, n ≥ 2. 𝛾sp(G) = n. When one or two edges added with C3n strong perfect domination number of the resulting graph either increase or remain same. Hence bcsp(G) ≥3. Let e1 = v1v3, e2 = v1v4, e3 = v1v5. X = {e1, e2, e3}.T = {v1, v7, v10, …, v3n- 2} is a strong perfect dominating set of G + X. |T| = n – 1.Therefore 𝛾sp (G +X) ≤ n – 1. Let S be any strong perfect dominating set of G + X. Since v1 is the unique maximum degree vertex in G + X, v1 belongs S. The subgraph induced by the vertices v6, v7, …, v3n - 1 is the path P3n – 6. Therefore 𝛾sp(P3n - 6) = 𝛾sp (P3(n – 2) ) = n - 2. Hence 𝛾sp (G + X) ≥ n - 1. Therefore 𝛾sp (G + X) = n - 1 < n = 𝛾sp(G). Hence bcsp(G) = 3. Theorem 3.5. bcsp(Dr, s) = s, r ≥ s, r, s ≥ 1. Proof. Let G = Dr,s , r, s ≥ 1. Let V(G) = {u, v, ui, vj/ 1 ≤ i ≤ r, 1 ≤ j ≤ s}, E(G) = {uv, uui, vvj/1 ≤ i ≤ r, 1 ≤ j ≤ s }. 𝛾sp(G) = 2. Let r ≥ s, r, s ≥ 1, 𝛾sp(G + X) = 1 if and only if G + X must have a full degree vertex. It is possible only if u is adjacent with v1, v2, …, vs or v is adjacent with u1, u2, …, ur. Since r ≥ s, X = {uvj/ 1≤j≤s}. u is the unique full degree vertex of G + X. Therefore 𝛾sp(G + X) = 1 < 𝛾sp(G). Hence bcsp(G) = s. Theorem 3.6. bcsp(Hn) = 1, n ≥ 4. Proof: Let G = Hn, n ≥ 4. Let V(G) = {v, vi, ui / 1≤ i ≤ n - 1}, E(G) = {vvi, viui /1≤ 𝑖 ≤ 𝑛 − 1} ∪{ vnv1} ∪ {vivi+1 /1≤ i ≤ n-2}. 𝛾sp(G) = n, n ≥ 5. deg v = n - 1, deg vi = 4, deg ui = 1, 1 ≤ 𝑖 ≤ 𝑛 − 1. Case (1). Let n ≥ 5. Let e = u1un - 1. T = {v, u1, u2, …, un-2} and {v, u2, u3, …, un - 1} are some strong perfect dominating sets of G + e. |T| = n - 1. Therefore 𝛾sp (G + e) ≤n - 1. Let S be any strong perfect dominating set of G + e. There are n – 3 pendent vertices, either n – 3 pendent vertices belong to S or their support vertices belong to S. v is the unique maximum degree vertex of G + e. Hence v belongs to S. Since u1 and un - 1 are adjacent either u1 or un - 1 belong to S. Therefore 𝛾sp(G + e) ≥ n - 1. Hence 𝛾sp(G + e) = n − 1 < 𝛾sp(G). Hence bcsp(G) = 1. Case (2). Let n = 4. 𝛾sp(G) = 3. Let e = v1u3. {v1, u2} is the unique 𝛾sp - set of G + e. Therefore 𝛾sp (G + e) =2 <3 = 𝛾sp(G). Hence bcsp(G) = 1. 70 Govindalakshmi T S and Meena N Theorem 3.8. bcsp (Km,n) = { 𝑛 − 1 𝑖𝑓 𝑚 = 𝑛, 𝑚, 𝑛 ≥ 2 1 𝑖𝑓 𝑚 = 2, 𝑛 ≥ 3, 𝑚 ≠ 𝑛, 𝑚 < 𝑛 𝑛 − 𝑚 𝑖𝑓 𝑚 ≠ 𝑛, 𝑚 < 𝑛, 𝑚 ≥ 3, 𝑛 ≥ 4 Proof. Let G = Km, n, m, n ≥ 2. V(G) = {vi, uj / 1≤ i≤ m, 1≤ j≤ n}. Case (1). Let m = n, m, n ≥ 2. 𝛾sp(G) = 2. 𝛾sp(G + X) = 1 if and only if G + X must have a full degree vertex. It is possible only if any ui is adjacent with all other uj or vi is adjacent with all other vj, i ≠ j,1 ≤ j≤ n. Therefore, ui or vi is a full degree vertex of G + X. Let X = {uiuj /1 ≤ j≤n and j ≠i} or {vivj /1 ≤ j≤ n and i ≠j}. |X| = n – 1. Therefore 𝛾sp (G + X) =1 < 𝛾sp(G). Hence bcsp(G) = n - 1. Case (2). Let m ≠ n, m