ISSN 2148-838Xhttps://doi.org/10.13069/jacodesmath.1056581 J. Algebra Comb. Discrete Appl. 9(1) • 47–55 Received: 16 May 2021 Accepted: 19 August 2021 Journal of Algebra Combinatorics Discrete Structures and Applications Protection of a network by complete secure domination Research Article Girish V. Rajasekharaiah, Usha P. Murthy, Umesh Subramanya Abstract: A complete secure dominating set of a graph G is a dominating set D ⊆ V (G) with the property that for each v ∈ D, there exists F = {vj|vj ∈ N(v) ∩ (V (G) − D)}, such that for each vj ∈ F , (D −{v}) ∪{vj} is a dominating set. The minimum cardinality of any complete secure dominating set is called the complete secure domination number of G and is denoted by γcsd(G). In this paper, the bounds for complete secure domination number for some standard graphs like grid graphs and stacked prism graphs in terms of number of vertices of G are found and also the bounds for the complete secure domination number of a tree are obtained in terms of different parameters of G. 2010 MSC: 05C69 Keywords: Domination, Secure domination, Complete secure domination 1. Introduction The graphs considered here are undirected, finite, connected, without multiple edges or loops and without isolated vertices. As usual n and q denote the number of vertices and edges of a graph G. For basic graph theoretic notation and terminology we refer to [4]. A set of vertices D is said to dominate the graph G if for each vertex v ∈ V (G)−D , there is a vertex u ∈ D with v is adjacent to u. The minimum cardinality of any dominating set is called the domination number of G and it is denoted by γ(G). A secure dominating set X of a graph G is a dominating set with the property that each vertex u ∈ V (G)−X is adjacent to a vertex v ∈ X such that(X −{v})∪{u} is dominating set. The minimum cardinality of such a set is called the secure domination number, denoted by γs(G). The Cartesian graph product G1×G2 called graph product of graphs G1 = (V1,E1) and G2 = (V2,E2) with disjoint vertex sets is the graph with the vertex set V1×V2 and u = (u1,u2) adjacent with v = (v1,v2) whenever [u1 = v1 and u2 adj v2] or [u2 = v2 and u1 adj v1]. Girish V. Rajasekharaiah, (Corresponding Author), Umesh Subramanya; Department of Science and Human- ities, PES University (EC Campus), Electronic City, Bengaluru, Karnataka, India (email: girishvr1@pes.edu, giridsi63@gmail.com, umeshsubbu@gmail.com). Usha P. Murthy; Department of Mathematics, Siddaganga Institute of Technology, B.H.Road, Tumakuru Kar- nataka, India (email: ushapmurhty@yahoo.com). 47 https://orcid.org/0000-0002-0036-6542 https://orcid.org/0000-0001-9855-1887 https://orcid.org/0000-0001-9672-8603 G. V. Rajasekharaiah et.al. / J. Algebra Comb. Discrete Appl. 9(1) (2022) 47–55 A friendship graph Fn is the graph obtained by joining n copies of C3 with a common vertex. A vertex of degree one is called an end vertex and a vertex adjacent to an end vertex is called non-end vertex. A two-dimensional grid graph Gm,n is the Cartesian product Pm ×Pn of path graphs on m and n vertices. A stacked prism graph is the Cartesian product of Cm ×Pn. The protection of a (simple) graph G = (V,E) involves placing a set (possibly empty) of guards at each vertex, and it is assumed that a guard can deal with a problem (called an attack) at any vertex in its closed neighborhood. Various strategies(i.e., rules for guard placements) have been devised, under each of which the entire graph G may be considered protected. The minimum number of guards required for protection under each strategy is clearly of interest. The concept of secure domination was introduced by Cockayne et.al. [3]. Later this concept was studied extensively in [1, 2]. In social network theory, we can assume the graph nodes as message centers and its edges as trans- mission lines. The message is transferred through the transmission line from one message center to another. The intent of this process is to transfer the messages to all message centers with minimum num- ber of message centers. To find all the minimum message centers, we can make use of domination and these minimum message centers are called as domination message centers. And if any of the domination message centers has an issue in sending the message, then it’s neighbor message center should act as a domination message center to complete the process. This solution is illustrated in secure domination con- cept, the drawback in this secure domination concept is that, it is just mentioned to select their neighbors as domination message centers, but not mentioned about which particular neighbor has to be chosen as a domination message center to achieve the objective or to complete the process. So, to overcome these problems we introduce a new concept called as complete secure domination with which one can select a neighbor as domination message centers. So that, we would be able to provide an analogy to retrieve a more efficient and robust domination message centers to solve the above mentioned issue and to transfer messages in a more faster and constructive manner. v1 e1 v2 v7 e7 e26 e27 e3 e4 v5 e8 v6 e6 v8 v14 v3 e5 v4 e28 e11 e13 e14 v15 v16 e9 e9 v9 v13 e15 e19 e20 e10 e12 e16 v17 v18 v10 e24 e17 e18 e21 v11 e25 v12 v20 v19 e22 e23 v21 Figure 1. Example for complete secure domination Minimum dominating set D = {v5,v4,v11,v13,v18,v17,v21}. Minimum secure dominating set C = {v6,v2,v3,v9,v13,v18,v17,v21}. Minimum complete secure dominating set F = {v6,v2,v3,v9,v13,v18,v17,v21,v15}. |D| = 7, |C| = 8, |F| = 9 48 G. V. Rajasekharaiah et.al. / J. Algebra Comb. Discrete Appl. 9(1) (2022) 47–55 A complete secure dominating set of a graph G is a dominating set D ⊆ V (G) with the property that for each v ∈ D, there exists F = {vj|vj ∈ N(v)∩(V (G)−D)}, such that for each vj ∈ F, (D−{v})∪{vj} is a dominating set. The minimum cardinality of any complete secure dominating set is called the complete secure domination number of G and is denoted by γcsd(G). 2. Complete secure domination for standard graphs Theorem 2.1. For any path Pn, γcsd(Pn) = dn2e. Theorem 2.2. For any wheel graph Wn, γcsd(Wn) = dn3e. Theorem 2.3. For any cycle Cn, γcsd(Cn) = dn2e. Theorem 2.4. For any friendship graph Fn with n vertices, γcsd(Fn) = dn3e. 3. Main results Theorem 3.1. For any graph G = P2 ×Pn, γcsd(G) = n,n ≥ 2. Proof. Let V (P2×Pn) = {(ui,vs),s = 1,2,3, . . . ,n}i=2i=1 be the vertices of first and second row, respec- tively. We consider the following cases. Case 1. Suppose n is even. Let A = {(u1,vs),s = 2p,1 ≤ p ≤ n2} and B = {(u2,vs),s = 2p − 1,1 ≤ p ≤ n 2 } with |A| = n 2 and |B| = n 2 . Let D = A∪B, every neighborhood vertex of V (G)−D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi})∪{vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = n2 + n 2 = n. Case 2. Suppose n is odd. Let A = {(u1,vs),s = 2p,1 ≤ p ≤ n−12 } and B = {(u2,vs),s = 2p − 1,1 ≤ p ≤ n+1 2 } with |A| = n−1 2 and |B| = n+1 2 . Let D = A∪B, every neighborhood vertex of V (G)−D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi}) ∪{vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = n−12 + n+1 2 = n. The proof is complete. Theorem 3.2. For any graph G = P3 ×Pn,n ≥ 2, γcsd(G) =   3n 2 n is even 3n−1 2 n is odd. Proof. Let V (P3 ×Pn) = {(ui,vs),s = 1,2,3, . . . ,n}i=3i=1 be the vertices of first, second and thrid row, respectively. We consider the following cases. Case 1. Suppose n is even. Let A = {(ur,vs),s = 2p,1 ≤ p ≤ n2 ,r = 1,3} and B = {(ur,vs),s = 2p− 1,1 ≤ p ≤ n 2 ,r = 2} with |A| = 2 ∗ n 2 and |B| = n 2 . Let D = A ∪ B, every neighborhood vertex of V (G) − D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi})∪{vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = n + n2 = 3n 2 . 49 G. V. Rajasekharaiah et.al. / J. Algebra Comb. Discrete Appl. 9(1) (2022) 47–55 Case 2. Suppose n is odd. Let A = {(ur,vs),s = 2p,1 ≤ p ≤ n−12 ,r = 1,3} and B = {(ur,vs),s = 2p− 1,1 ≤ p ≤ n+1 2 ,r = 2} with |A| = 2(n−1 2 ) and |B| = n+1 2 . Let D = A∪B, every neighborhood vertex of V (G) −D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D−{vi})∪{vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = n−1 + n+12 = 3n−1 2 . The proof is complete. Theorem 3.3. For any graph G = P4 ×Pn, γcsd(G) = 2n,n ≥ 2. Proof. Let V (P4×Pn) = {(ui,vs),s = 1,2,3, . . . ,n}i=4i=1 be the vertices of first, second, thrid and fourth row, respectively. We consider the following cases. Case 1. Suppose n is even. Let A = {(ur,vs),s = 2p,1 ≤ p ≤ n2 ,r = 1,3} and B = {(ur,vs),s = 2p−1,1 ≤ p ≤ n 2 ,r = 2,4} with |A| = 2∗ n 2 and |B| = 2∗ n 2 . Let D = A∪B, every neighborhood vertex of V (G)−D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi})∪{vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = n + n = 2n. Case 2. Suppose n is odd. Let A = {(ur,vs),s = 2p,1 ≤ p ≤ n−12 ,r = 1,3} and B = {(ur,vs),s = 2p− 1,1 ≤ p ≤ n+1 2 ,r = 2,4} with |A| = 2(n−1 2 ) and |B| = 2(n+1 2 ). Let D = A∪B, every neighborhood vertex of V (G)−D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D−{vi})∪{vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = n−1 + n + 1 = 2n. The proof is complete. Theorem 3.4. For any graph G = P5 ×Pn,n ≥ 2, γcsd(G) =   5n 2 n is even 5n−1 2 n is odd. Proof. Let V (P5 ×Pn) = {(ui,vs),s = 1,2,3, . . . ,n}i=5i=1 be the vertices of first, second, third, fourth and fifth row, respectively. We consider the following cases. Case 1. Suppose n is even. Let A = {(ur,vs),s = 2p,1 ≤ p ≤ n2 ,r = 1,3,5} and B = {(ur,vs),s = 2p− 1,1 ≤ p ≤ n 2 ,r = 2,4} with |A| = 3∗n 2 and |B| = 2∗n 2 . Let D = A∪B, every neighborhood vertex of V (G)−D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D−{vi})∪{vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+|B| = 3n2 +n = 5n 2 . Case 2. Suppose n is odd. Let A = {(ur,vs),s = 2p,1 ≤ p ≤ n−12 ,r = 1,3,5} and B = {(ur,vs),s = 2p − 1,1 ≤ p ≤ n+1 2 ,r = 2,4} with |A| = 3(n−1 2 ) and |B| = 2(n+1 2 ). The set D = A ∪ B is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = 3(n−12 ) + n + 1 = 5n−1 2 . The proof is complete. 50 G. V. Rajasekharaiah et.al. / J. Algebra Comb. Discrete Appl. 9(1) (2022) 47–55 Theorem 3.5. For any graph G = Pm ×Pn,m,n ≥ 2, γcsd(G) =   mn 2 m is even mn 2 m is odd, n is even mn−1 2 m is odd, n is odd. Proof. Let V (Pm × Pn) = {(ur,vs),s = 1,2,3, . . . ,n}r=mr=1 be the vertices of first, second, third, . . . , mth row, respectively. We consider the following cases. Case 1. Suppose m is even and n is even. Let A = {(ur,vs),r = 2p− 1,1 ≤ p ≤ m2 ,s = 2q,1 ≤ q ≤ n 2 } and B = {(ur,vs),r = 2p,1 ≤ p ≤ m 2 ,s = 2q − 1,1 ≤ q ≤ n 2 } with |A| = mn 4 and |B| = mn 4 . Let D = A∪B, every neighborhood vertex of V (G)−D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi}) ∪{vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A| + |B| = mn 4 + mn 4 = mn 2 . Case 2. Suppose m is even and n is odd. Let A = {(ur,vs),r = 2p − 1,1 ≤ p ≤ m2 ,s = 2q,1 ≤ q ≤ n−1 2 } and B = {(ur,vs),r = 2p,1 ≤ p ≤ m 2 ,s = 2q − 1,1 ≤ q ≤ n+1 2 } with |A| = m(n−1) 4 and |B| = m(n+1) 4 . Let D = A ∪ B, every neighborhood vertex of V (G) −D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi}) ∪ {vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = m(n−1) 4 + m(n+1) 4 = mn 2 . Case 3. Suppose m is odd and n is even. Let A = {(ur,vs),r = 2p − 1,1 ≤ p ≤ m+12 ,s = 2q,1 ≤ q ≤ n 2 } and B = {(ur,vs),r = 2p,1 ≤ p ≤ m−1 2 ,s = 2q − 1,1 ≤ q ≤ n 2 } with |A| = (m+1)n 4 and |B| = (m−1)n 4 . Let D = A ∪ B, every neighborhood vertex of V (G) −D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi}) ∪ {vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = (m+1)n 4 + (m−1)n 4 = mn 2 . Case 4. Suppose m is odd and n is odd. Let A = {(ur,vs),r = 2p− 1,1 ≤ p ≤ m+12 ,s = 2q,1 ≤ q ≤ n−1 2 } and B = {(ur,vs),r = 2p,1 ≤ p ≤ m−1 2 ,s = 2q−1,1 ≤ q ≤ n+1 2 } with |A| = (m+1)(n−1) 4 and |B| = (m−1)(n+1) 4 . Let D = A∪B, every neighborhood vertex of V (G) −D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi}) ∪ {vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = (m+1)(n−1) 4 + (m−1)(n+1) 4 = mn−1 2 . The proof is complete. Theorem 3.6. For any graph, G = C3 ×Pn, γcsd(G) = n,n ≥ 3. Proof. Let V (C3 ×Cn) = {(ui,vs),s = 1,2,3, . . . ,n}i=3i=1 be the vertices of first, second and third row, respectively. The set A = {(u1,vs),s = 1,2,3, . . . ,n} with |A| = n. Since A is the γ-set of G and therefore A is the γcsd-set of G. Hence γcsd(G) = n. Theorem 3.7. For any graph, G = C4 ×Cn, γcsd(G) = 2n,n ≥ 3. 51 G. V. Rajasekharaiah et.al. / J. Algebra Comb. Discrete Appl. 9(1) (2022) 47–55 Proof. Let V (C3 × Cn) = {(ui,vs),s = 1,2,3, . . . ,n}i=4r=1 be the vertices of first, second, third and fourth row, respectively. The set D = {(u1,vs),(u3,vs),s = 1,2,3, . . . ,n} with |D| = 2n. Since every neighborhood vertex of V (G)−D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D−{vi})∪{vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = 2n. Theorem 3.8. For any graph G = Cm ×Pn,m 6= 3,n ≥ 3, γcsd(G) =   mn 2 m is even or odd and n is even mn 2 m is even, n is odd. mn−1 2 m is odd, n is odd. Proof. Let V (Cm × Cn) = {(ur,us),s = 1,2,3, . . . ,n}r=mr=1 be the vertices of first, second, third, . . . mth row, respectively. We consider the following cases. Case 1. Suppose m is even and n is even. Let A = {(ur,vs),r = 2p− 1,1 ≤ p ≤ m2 ,s = 2q,1 ≤ q ≤ n 2 } and B = {(ur,vs),r = 2p,1 ≤ p ≤ m 2 ,s = 2q − 1,1 ≤ q ≤ n 2 } with |A| = mn 4 and |B| = mn 4 . Let D = A∪B, every neighborhood vertex of V (G)−D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi}) ∪{vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A| + |B| = mn 4 + mn 4 = mn 2 . Case 2. Suppose m is even and n is odd. Let A = {(ur,vs),r = 2p − 1,1 ≤ p ≤ m2 ,s = 2q,1 ≤ q ≤ n−1 2 } and B = {(ur,vs),r = 2p,1 ≤ p ≤ m 2 ,s = 2q − 1,1 ≤ q ≤ n+1 2 } with |A| = m(n−1) 4 and |B| = m(n+1) 4 . Let D = A∪B, every neighborhood vertex of V (G)−D is in D, D is the complete secure dominating set of Pm ×Pn. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi}) ∪ {vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = m(n−1) 4 + m(n+1) 4 = mn 2 . Case 3. Suppose m is odd and n is even. Let A = {(ur,vs),r = 2p − 1,1 ≤ p ≤ m+12 ,s = 2q,1 ≤ q ≤ n 2 } and B = {(ur,vs),r = 2p,1 ≤ p ≤ m−1 2 ,s = 2q − 1,1 ≤ q ≤ n 2 } with |A| = (m+1)n 4 and |B| = (m−1)n 4 . Let D = A ∪ B, every neighborhood vertex of V (G) −D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (G), (D −{vi}) ∪ {vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = (m+1)n 4 + (m−1)n 4 = mn 2 . Case 4. Suppose m is odd and n is odd. Let A = {(ur,vs),r = 2p− 1,1 ≤ p ≤ m+12 ,s = 2q,1 ≤ q ≤ n−1 2 } and B = {(ur,vs),r = 2p,1 ≤ p ≤ m−1 2 ,s = 2q−1,1 ≤ q ≤ n+1 2 } with |A| = (m+1)(n−1) 4 and |B| = (m−1)(n+1) 4 . Let D = A∪B, every neighborhood vertex of V (G) −D is in D, D is the complete secure dominating set of G. Hence γcsd(G) ≤ |D|. If γcsd(G) < |D|, then there exits at least one vertex say vj ∈ V (Pm ×Pn), (D −{vi}) ∪ {vj},vi ∈ D is not a dominating set. Therefore D is the γcsd-set of G. Hence γcsd(G) = |D| = |A|+ |B| = (m+1)(n−1) 4 + (m−1)(n+1) 4 = mn−1 2 . The proof is complete. Theorem 3.9. For any graph G, if every non-end vertex is adjacent with an end-vertex then, γcsd(G) = p, where p is the number of end-vertices of G. 52 G. V. Rajasekharaiah et.al. / J. Algebra Comb. Discrete Appl. 9(1) (2022) 47–55 Proof. Let A = {vi ∈ V (G)|d(vi) = 1}, B = {vj ∈ V (G) − A|vj ∈ N(vi)} and C = (A −{vr}) ∪ {vj},vr ∈ A,vj ∈ B ∩ N(vi). Let D = A or C. Now for each v ∈ D, there exists F = {vj|vj ∈ N(v) ∩ V (G) − D}, such that for each vj ∈ F, (D −{v}) ∪{vj} is a dominating set. Hence D is a complete secure dominating set of G. Now we show that there exists no other minimum complete secure dominating set other than D. If suppose F 6= D is a minimum complete secure domination set of G with |F| < |D|, then either F is not a dominating set or for atleast one vertex v ∈ F there exists vj ∈ N(v) such that (F −{v})∪{vj} is not a dominating set of G. Hence γcsd(G) = |D| = p. Corollary 3.10. For any graph G, if every non-end vertex is adjacent with an end-vertex then, γcsd(G) = γns(G), where γns(G) is the nonsplit domination number of G. Proof. If every non-end vertex is adjacent with an end-vertex then, γns(G) = p, p is the number of end vertices of G, then by Theorem 3.9, the result follows. Theorem 3.11. For any tree T with n vertices, γcsd(T) ≤ p+dn−2p2 e,p is the number of end vertices of T. Proof. Let A = {vi ∈ V (T)|d(vi) = 1} and B = {vj ∈ V (T) − A|vj ∈ N(vi)}. We consider the following cases. Case 1. If every non-end vertex of T is adjacent to an end-vertex then by Theorem 3.9, γcsd(T) = p. Case 2. If atleast one vertex say vj ∈ V (G), vj is not adjacent to an end-vertex say vi ∈ A, then the graph T − (A∪B) will be a tree with n− 2p vertices and partition the vertex set of T − (A∪B) into two disjoint sets say R and S such that vi ∈ R and vj ∈ S,vi ∈ N(vj) and |R| ≥ |S|. Now consider the set D = A ∪ R, then for each v ∈ D, there exists F = {vj|vj ∈ N(v) ∩ V (T) − D}, such that for each vj ∈ F, (D −{v}) ∪{vj} is a dominating set. Therefore F is the complete secure dominating set of G. Hence γcsd(T) ≤ F = p +dn−2p2 e. Theorem 3.12. For any graph G = K2 ×K1,n−1, γcsd(G) = n,n ≥ 3. Proof. Let V (K2) = {u1,u2} and V (K1,n−1) = {v1,v2,v3, . . . ,vn} with d(v1) = n − 1. Let V (G) = V (K2 × K1,n−1) = A ∪ B, A = {(ui,vj) ∈ V (G)/d((ui,vj)) = n}, B = {(ur,vs) ∈ V (G) − A} with |A| = 2, |B| = 2(n−1). Partition the vertex of B into disjoint vertex sets, B = H∪R such that (ui,vj) ∈ N((ur,vs)),(ui,vj) ∈ H,(ur,vs) ∈ R with |H| = |R| = n−1. Any minimum dominating set D of G has to contain two vertices say F = {(u1,v1),(u2,v1)} where {(u1,v1),(u2,v2)} ∈ A. Suppose D is a complete secure dominating set, then the induced graph M = 〈V (G)−({(u1,v1)} or {(u2,v1)})〉 will contains n−1 support vertices and by Theorem 3.9, γcsd(M) = n−1 and if γcsd(G) = n−1, then there exists at least one vertex say (ui,vj) ∈ V (G) which is not dominated by (D−{(um,vr)}∪(ui,vj),(um,vr) ∈ D∪N((ui,vj)). Therefore γcsd > n − 1. Since each vertex in B is of degree 2 and belongs to neighborhood of D, therefore the dominating set has to contain the vertices of H or R together with any vertex of A. Now consider the set K = H ∪{(u1,v1)}, for each vertex (ui,vj) ∈ K, there exists F = {(ur,vs)/(ur,vs) ∈ N((ui,vj)) ∩ (V (G) −D)}, such that for each (ur,vs) ∈ F, (D −{(ui,vj)}) ∪{(ur,vs)} is a dominating set. Hence K is a complete secure dominating set, γcsd = |K| = n. Definition 3.13. Planar honeycomb graphs are the graphs obtained by connecting some equal regular hexagons such that any two adjacent hexagons have one edge in common. The planar honeycomb lattice is also called benzoid and it is denoted by Bn. Theorem 3.14. For any planar honeycomb graph Bn with n vertices, n ≥ 6, γcsd(Bn) = dn2e. Proof. Let V (Bn) = {u1i,u2i,u3i, . . . ,upi, i = 1,2,3, . . . ,q} denotes the first, second, third, fourth,. . . ,pthrow, respectively. We consider the following cases. Case 1. When n = 6. In this case the graph B6 = C6. The result follows from Theorem 2(iii). 53 G. V. Rajasekharaiah et.al. / J. Algebra Comb. Discrete Appl. 9(1) (2022) 47–55 Figure 2. Example for Honeycomb graph Case 2. When n = 10. Then the graph B10 contains two cycles with one edge in common, which is isomorphic to the graph H, where V (H) = V (C6) ∪V (P4) and E(H) = E(C6) ∪E(P4) ∪e1 ∪e2, where e1 and e2 joins (v1,u1) and (v2,u2), where v1,v2 ∈ V (C6),v1 ∈ N(v2) and u1 and u2 are the end vetices of P4. Hence γcsd = γcsd(C6) + γcsd(P4) = 3 + 2 = dn2e. Case 3. When n ≥ 10. In this case. the planar honey comb graph can be obtained by adding an edge that connects the end vertices of m copies of either P1 or P2 or P3 or P4 with an adjacent vertices of B10. By using case 2 and Theorem 3.9, γcsd = γcsd(B10) + mγcsd(P1orP2orP3orP4) =5 + dn−10 2 e. =5 + dn 2 e−5. =dn 2 e. 4. Application Whenever we transfer a message from one mobile device which is in different signal range, to another mobile device which is in some other different signal range, then sometimes can be a loss of data or the message may be delivered after a long time. These are mainly due to the unstructured or unorganized way of locating message service systems and unsecured network. These problems can be solved using our complete secure domination. Through secure domination, we are providing the least or minimum number of message centers with which the entire block or chain of message centers can be covered and also secured. In this way, we propose the complete secure domination with minimum number of message centers to overcome the above mentioned issues. 54 G. V. Rajasekharaiah et.al. / J. Algebra Comb. Discrete Appl. 9(1) (2022) 47–55 References [1] M. Anderson, C. Barrientos, R. Brigham, J. Carrington, R. Vitray, J. Yellen, Maximum demand graphs for eternal security, J. Combin. Math. Combin. Comput. 61 (2007) 111–128. [2] S. Benecke, Higher order domination of graphs, Master Thesis, University of Stellenbosch (2004). [3] S. Benecke, E. J. Cockayne, C. M. Mynhardt, Secure total domination in graphs, Utilitas Math. 74 (2007) 247–259. [4] F. Harary, Graph theory, Addison-Wesely, Reading Mass, 1st Edition (1969). 55 https://mathscinet.ams.org/mathscinet-getitem?mr=2322206 https://mathscinet.ams.org/mathscinet-getitem?mr=2322206 https://mathscinet.ams.org/mathscinet-getitem?mr=2364004 https://mathscinet.ams.org/mathscinet-getitem?mr=2364004 https://doi.org/10.1201/9780429493768 Introduction Complete secure domination for standard graphs Main results Application References