Secure domination in P 5 P_{5} -free graphs Thanks: Research supported in part by the University of Johannesburg and the South African National Research Foundation Thanks: Corresponding author. Abstract A dominating set of a graph G G is a set S ⊆ V ⁡ ( G ) S\subseteq V(G) such that every vertex in V ⁡ ( G ) ∖ S V(G)\setminus S has a neighbor in S S , where two vertices are neighbors if they are adjacent. A secure dominating set of G G is a dominating set S S of G G with the additional property that for every vertex v ∈ V ⁡ ( G ) ∖ S v\in V(G)\setminus S , there exists a neighbor u u of v v in S S such that ( S ∖ { u } ) ∪ { v } (S\setminus\{u\})\cup\{v\} is a dominating set of G G . The secure domination number of G G , denoted by γ s ​ ( G ) \gamma_{s}(G) , is the minimum cardinality of a secure dominating set of G G . We prove that if G G is a P 5 P_{5} -free graph, then γ s ​ ( G ) ≤ 3 2 ​ α ​ ( G ) \gamma_{s}(G)\leq\frac{3}{2}\alpha(G) , where α ⁡ ( G ) \alpha(G) denotes the independence number of G G . We further show that if G G is a connected ( P 5 , H ) (P_{5},H) -free graph for some H ∈ { P 3 ∪ P 1 , K 2 ∪ 2 ​ K 1 , paw , C 4 } H\in\{P_{3}\cup P_{1},K_{2}\cup 2K_{1},{\rm paw},C_{4}\} , then γ s ​ ( G ) ≤ max ⁡ { 3 , α ⁡ ( G ) } \gamma_{s}(G)\leq\max\{3,\alpha(G)\} . We also show that if G G is a ( P 3 ∪ P 2 ) (P_{3}\cup P_{2}) -free graph, then γ s ​ ( G ) ≤ α ⁡ ( G ) + 1 \gamma_{s}(G)\leq\alpha(G)+1 . Keywords: Domination; Secure domination; Independence number; P_{5} -free graphs AMS subject classification: 05C69 1 Introduction All the graphs considered in this paper are finite, simple, and undirected. We use P_{n} , C_{n} , and K_{n} to denote the path , the cycle , and the complete graph , respectively on n vertices. For a graph G , we use V(G) and E(G) to denote the vertex set and the edge set of G , respectively. Two vertices u and v of G are adjacent if uv\in E(G) . The \emph{neighbors} of v in G are the vertices adjacent to v in G . For vertex disjoint graphs G and H , we use G\cup H to denote the disjoint union of G and H . For a positive integer m , we use mG to denote the disjoint union of m copies of G . Let \mathcal{F} be a family of graphs. A graph G is called \mathcal{F} -free if G does not contain any graph in \mathcal{F} as an induced subgraph. When \mathcal{F}=\{H\} (resp. \{H_{1},\ldots,H_{k}\} , k\geq 2 ), we use H -free (resp. (H_{1},\ldots,H_{k}) -free) graphs to denote the \mathcal{F} -free graphs. For some special graphs mentioned in this paper, we refer to Figure 1 . Figure 1: Some special graphs A set D\subseteq V(G) is a dominating set of G if every vertex in V(G)\setminus D is adjacent to at least one vertex in D . The domination number of G , denoted by \gamma(G) , is the minimum cardinality of a dominating set of G . The domination problem and its variants have been extensively studied in the literature. Domination in graphs and its variants have numerous applications and have been thoroughly explored from theoretical and algorithmic perspectives. For a detailed study of domination and its variants, we refer the reader to [ Haynes1 , Haynes2 , Haynes3 , HeYe-book ] . Secure domination in graphs is a variant of domination introduced by Cockayne et al. [ Cockayne05 ] in 2005. Since its birth, secure domination remained an active area of research (see [ Burger08 , Burger16 , Cockayne03 , Klostermeyer08 ] ). Consider a problem of defending the vertices of a graph G with guards against an attacker. The vertices of G may represent regions and at each vertex, at most one guard is located. The attacker can attack at one vertex of G at a time and can do two consecutive attacks. A guard can protect its position vertex and its every neighbor (possibly by moving to it). To defend against the attacker, only one guard can move at a time. If the attacker has already attacked one of the vertices of G where a guard is not placed, then in that case, one guard can move from its current position vertex to an adjacent vertex to stop the attack. Additionally, guards can still protect the vertices of G if a second attack occurs. The idea of secure domination was created as a response to this need, where the arrangements of defending the vertices of G both before and after the attack have been prevented. In order to fulfill the above requirement, a secure dominating set is formally defined as follows. A set S\subseteq V(G) is called a secure dominating set of G if S is a dominating set of G and for each v\in V(G)\setminus S , there exists a neighbor u of v in S such that (S\setminus\{u\})\cup\{v\} is a dominating set of G . The secure domination number of G , denoted by \gamma_{s}(G) , is the minimum cardinality of a secure dominating set of G . A set I\subseteq V(G) is an independent set if no two vertices in the set I are adjacent to each other. The independence number of G , denoted by \alpha(G) , is the maximum cardinality of an independent set of G . An independent set in G of cardinality \alpha(G) we call an \alpha -set of G . If I is a maximal independent set of G and v is an arbitrary vertex in V(G)\setminus I , then by the maximality of I the set I\cup\{v\} is not an independent set, implying that the vertex v has at least one neighbor in I . We state this well-known observation formally as follows. Observation 1 . Every maximal independent set of a graph G is a dominating set of G . 1.1 Related works By Observation 1 , for every graph G we have \gamma(G)\leq\alpha(G) . We note that \gamma_{s}(C_{5})=3 and \alpha(C_{5})=2 , implying that \gamma_{s}(G) can be larger than \alpha(G) . Merouane and Chellali [ merouane15 ] established the following upper bound on the secure domination number of a graph in terms of its independence number. Theorem 1 ( [ merouane15 ] ) . If G is a graph, then \gamma_{s}(G)\leq 2\alpha(G)-1 . A natural question arises whether we can improve the upper bound in Theorem 1 to \gamma_{s}(G)\leq c\alpha(G) , where c<2 for specific classes of graphs. Cockayne et al. [ Cockayne03 ] showed that c=\frac{3}{2} for the class of claw-free graphs. Theorem 2 ( [ Cockayne03 ] ) . If G is a claw-free graph, then \gamma_{s}(G)\leq\frac{3}{2}\alpha(G) . Since the class of 3K_{1} -free graphs is a subclass of the class of claw-free graphs, the upper bound in Theorem 2 also holds in the class of 3K_{1} -free graphs. We note that if G is a 3K_{1} -free graph, then \alpha(G)\leq 2 . Hence if G is a 3K_{1} -free graph, then \gamma_{s}(G)\leq 3 . Merouane and Chellali [ merouane15 ] proved that the upper bound in Theorem 2 also holds in the class of C_{3} -free graphs, that is, in K_{3} -free graphs. Theorem 3 ( [ merouane15 ] ) . If G is a C_{3} -free graph, then \gamma_{s}(G)\leq\frac{3}{2}\alpha(G) . We note that the upper bound in Theorem 3 is tight since if G is the graph obtained from the disjoint union of copies of C_{5} , then the resulting graph G is C_{3} -free and satisfies \gamma_{s}(G)=\frac{3}{2}\alpha(G) . Merouane and Chellai [ merouane15 ] also showed that if G is a bipartite graph, then \gamma_{s}(G)\leq\alpha(G) . Recently, Degawa and Saito [ degawa23 ] established that the secure domination number of a C_{5} -free graph is at most its independence number. Theorem 4 ( [ degawa23 ] ) . If G is a C_{5} -free graph, then \gamma_{s}(G)\leq\alpha(G) . We note that the bounds for bipartite graphs and C_{5} -free graphs are tight since a star graph G=K_{1,n} is a C_{5} -free bipartite graph and satisfies \gamma_{s}(G)=\alpha(G) [ Cockayne05 ] . 2 Main results and motivation The class of P_{4} -free graphs is a subclass of the class of C_{5} -free graphs. Hence as a consequence of Theorem 4 , if G is a P_{4} -free graph, then \gamma_{s}(G)\leq\alpha(G) . Moreover, two linear algorithms have been independently developed to compute the secure domination number of a P_{4} -free graph (see [ Araki19 , jha19 ] ). Hence it is of interest to find a superclass of the class of P_{4} -free graphs that yields a tight upper bound on the secure domination number of a graph in terms of its independence number. In this paper, we consider such a superclass of P_{4} -free graphs, namely P_{5} -free graphs. We shall prove the following result, a proof of which is given in Section 4 . Theorem 5 . If G is a P_{5} -free graph, then \gamma_{s}(G)\leq\frac{3}{2}\alpha(G) . Given a graph G and a positive integer k , the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k . Merouane and Chellali [ merouane15 ] showed that secure domination problem is \mathbf{NP} -complete for split graphs. Foldes and Hammer [ Foldes ] proved that G is a split graph if and only if G is a (2K_{2},C_{4},C_{5}) -free graph. Since the class of split graphs is a subclass of the class of C_{5} -free graphs, as a consequence of Theorem 4 we infer that if G is a split graph, then \gamma_{s}(G)\leq\alpha(G) . Recently, Chen et al. [ Chen25 ] have proved that if G is a 2K_{2} -free graph, then \gamma_{s}(G)\leq\alpha(G)+1 . Note that the class 2K_{2} -free graphs is a superclass of the class of split graphs. We are therefore interested in a superclass of the class of 2K_{2} -free graphs that yields a tight upper bound on the secure domination number in terms of its independence number. We consider such a superclass of 2K_{2} -free graphs, namely (P_{3}\cup P_{2}) -free graphs. We shall prove the following result, a proof of which is given in Section . Theorem 6 . If G is a (P_{3}\cup P_{2}) -free graph, then \gamma_{s}(G)\leq\alpha(G)+1 . Although the bound of Theorem 6 is tight, we show that the bound can be improved for some subclasses of (P_{3}\cup P_{2}) -free graphs. A proof of the following result is given in Section . Theorem 7 . If G is an H -free graph, where H\in\{P_{3}\cup P_{1},K_{2}\cup 2K_{1}\} , then \gamma_{s}(G)\leq\max\{3,\alpha(G)\} . We also investigate a subclass of the P_{5} -free graphs, namely connected (P_{5},H) -free graphs where H\in\{{\rm paw},C_{4}\} . By using the structural properties of such graphs, we shall prove the following results, proofs of which are given in Sections and , respectively. Theorem 8 . If G is a connected (P_{5},{\rm paw}) -free graph, then \gamma_{s}(G)\leq\max\{3,\alpha(G)\} . Theorem 9 . If G is a connected (P_{5},C_{4}) -free graph, then \gamma_{s}(G)\leq\max\{3,\alpha(G)\} . We summarize our results in Table 1 . In this table, we present upper bounds on the secure domination number, \gamma_{s}(G) , of a graph G depending on the structural properties of the graph G . Graph Class \mathcal{C} \gamma_{s} -bound for G\in\mathcal{C} reference General graphs 2\alpha(G)-1 [ merouane15 ] Claw-free graphs \frac{3}{2}\alpha(G) [ Cockayne03 ] C_{3} -free graphs \frac{3}{2}\alpha(G) [ merouane15 ] Paw-free graphs \frac{3}{2}\alpha(G) [Corollary ] Bipartite graphs \alpha(G) [ merouane15 ] C_{5} -free graphs \alpha(G) [ degawa23 ] P_{5} -free graphs \frac{3}{2}\alpha(G) [Theorem 5 ] (P_{3}\cup P_{2}) -free graphs \alpha(G)+1 [Theorem 6 ] (P_{3}\cup P_{1}) -free graphs \max\{3,\alpha(G)\} [Theorem ] (K_{2}\cup 2K_{1}) -free graphs \max\{3,\alpha(G)\} [Theorem ] Connected (P_{5},{\rm paw}) -free graphs \max\{3,\alpha(G)\} [Theorem 8 ] Connected (P_{5},C_{4}) -free graphs \max\{3,\alpha(G)\} [Theorem 9 ] Table 1: Upper bounds on the secure domination number of a graph G 3 Notation, terminology and preliminary results Let G be a graph. The (open) neighborhood of a vertex v\in V(G) , denoted by N_{G}(v) , is the set of neighbors of v in G . The closed neighborhood of a vertex v\in V(G) is the set N_{G}[v]=N_{G}(v)\cup\{v\} . For a set X\subseteq V(G) , the (open) neighborhood of X , denoted by N_{G}(X) , is the set \{v\in V(G)\setminus X\,\colon v\text{ is adjacent to a vertex in }X\} . The closed neighborhood of X is the set N_{G}[X]=N_{G}(X)\cup X . We simply use N(v),N[v],N(X) , and N[X] to denote N_{G}(v),N_{G}[v],N_{G}(X), and N_{G}[X] , respectively when the context of the graph G is clear. We use G[X] to denote the subgraph of G induced by the vertices in X . A vertex v dominates itself and all its neighbors. A set X\subseteq V(G) is called a clique of G if every pair of vertices of X are adjacent. For disjoint subsets X and Y of V(G) , G[X,Y] denotes the set of edges \{e\in E(G)\,\colon e has one endpoint in X and the other endpoint in Y\} . If the graph G is clear from the context, we write [X,Y] rather than G[X,Y] . We say that G[X,Y] is complete if every vertex in X is adjacent to every vertex in Y in G . For a given positive integer k , we use the notation [k] to denote the set \{1,\ldots,k\} . For a set D\subseteq V(G) and a vertex u\in D , the D -external private neighborhood of u , denoted by {\rm epn}(u,D) , is the set \{v\in V(G)\setminus D\,\colon N(v)\cap D=\{u\}\} . A vertex in {\rm epn}(u,D) is a D -external private neighbor of u . We say that a vertex v\in V(G)\setminus D is D - defended if there exists a vertex u\in N(v)\cap D such that (D\setminus\{u\})\cup\{v\} is a dominating set of G . Specifically, we say that v\in V(G)\setminus D is D - defended by a vertex u if u\in N(v)\cap D and (D\setminus\{u\})\cup\{v\} is a dominating set of G . We note that D is a secure dominating set of G if and only if every vertex in V(G)\setminus D is D -defended. We also note that if D is a dominating set of G and {\rm epn}(u,D)=\emptyset for some u\in D , then every neighbor of u in V(G)\setminus D is D -defended by u . We state this observation formally as follows. Observation 2 . If D is a dominating set of a graph G and {\rm epn}(u,D)=\emptyset for some vertex u\in D , then every neighbor of u that belongs to V(G)\setminus D is D -defended by u . As a consequence of Observation 2 , if D is a dominating set of G and {\rm epn}(u,D)=\emptyset for every u\in D , then every vertex in V(G)\setminus D is D -defended, implying that D is a secure dominating set of G . For a given dominating set D of G , we partition D as A_{D}\cup B_{D} , where the sets A_{D} and B_{D} are defined as follows. \displaystyle\bullet\, \displaystyle\,A_{D}=\{u\in D\,\colon\text{ there exists a neighbor of }u\text{ in }V(G)\setminus D\text{ that is not }D\text{-defended.}\} ( \mathcal{P}_{1} ) \displaystyle\bullet\, \displaystyle\,B_{D}=D\setminus A_{D}. We now prove the following useful lemma. We remark that some of the facts that appear in the following lemma have appeared implicitly in several papers (see [ Cockayne03 , merouane15 ] ). Lemma 1 . Let D be a dominating set of G and A_{D}\cup B_{D} be a partition of D as defined in ( P 1 ) . (a) If A_{D}=\emptyset , then D is a secure dominating set of G . (b) If a vertex v in V(G)\setminus D is not D -defended, then N(v)\cap D\subseteq A_{D} . (c) If u is a vertex in A_{D} , then {\rm epn}(u,D)\neq\emptyset . (d) If a vertex v in V(G)\setminus D is not D -defended, then for every neighbor u of v in D , the vertex v has a non-neighbor in {\rm epn}(u,D) , that is, {\rm epn}(u,D)\setminus N(v)\neq\emptyset . (e) If D^{\prime} is a superset of D , then A_{D^{\prime}}\subseteq A_{D} and B_{D}\subseteq B_{D^{\prime}} , where A_{D^{\prime}}\cup B_{D^{\prime}} is a partition of D^{\prime} as defined in ( P 1 ) . Proof. Parts (a) and (b) follow by the definition of the sets A_{D} and B_{D} , while part (c) follows by Observation 2 . To prove part (d), let v be a vertex in V(G)\setminus D that is not D -defended. Suppose, to the contrary, that there exists a neighbor u\in D of v such that v is adjacent to every vertex in {\rm epn}(u,D) . We note that this also includes the case when {\rm epn}(u,D)=\emptyset . However, then, (D\setminus\{u\})\cup\{v\} is a dominating set of G , contradicting the fact that the vertex v is not D -defended. To prove part (e), let D^{\prime} be a superset of D . Since the property of being a dominating set is superhereditary, D^{\prime} is a dominating set of G . We partition D^{\prime} as A_{D^{\prime}}\cup B_{D^{\prime}} as defined in ( P 1 ). Let u be a vertex in A_{D^{\prime}} . By (c), {\rm epn}(u,D^{\prime})\neq\emptyset . First we show that u\in D . Suppose, to the contrary, that u\notin D . Since D is a dominating set of G , every vertex in V(G)\setminus D is adjacent to a vertex in D . Moreover since D\subseteq D^{\prime} , we have V(G)\setminus D^{\prime}\subseteq V(G)\setminus D . This implies that every vertex x in {\rm epn}(u,D^{\prime}) is adjacent to a vertex in D that is different than u (since, by supposition, u\notin D ), contradicting the fact that {\rm epn}(u,D^{\prime})\neq\emptyset . Hence, u\in D . Since u\in A_{D^{\prime}} , by the definition of A_{D^{\prime}} , there exists a neighbor of u in V(G)\setminus D^{\prime} , say w , that is not D^{\prime} -defended. Thus, by part (d), we have {\rm epn}(u,D^{\prime})\setminus N(w)\neq\emptyset . Since D\subseteq D^{\prime} , we have w\in V(G)\setminus D^{\prime}\subseteq V(G)\setminus D and {\rm epn}(u,D^{\prime})\subseteq{\rm epn}(u,D) , and so {\rm epn}(u,D)\setminus N(w)\neq\emptyset , implying that w is not D -defended by u . Thus, u\in A_{D} . Since u is an arbitrary vertex in A_{D^{\prime}} , we infer that A_{D^{\prime}}\subseteq A_{D} . Thus since D\subseteq D^{\prime} , we have B_{D}=D\setminus A_{D}\subseteq D^{\prime}\setminus A_{D}\subseteq D^{\prime}\setminus A_{D^{\prime}}=B_{D^{\prime}} , that is, B_{D}\subseteq B_{D^{\prime}} . ∎ Let I is an \alpha -set of G , and so I is a maximum independent set in G . Further, let u\in I such that {\rm epn}(u,I)\neq\emptyset . If there exist two vertices x,y\in{\rm epn}(u,I) such that xy\notin E(G) , then (I\setminus\{u\})\cup\{x,y\} is an independent set larger than I , a contradiction. Hence, {\rm epn}(u,I) is necessarily a clique. This fact has appeared implicitly in several papers (see, for example, [ degawa23 , merouane15 ] ). We state this property of a maximum independent set formally as follows. Lemma 2 ( [ degawa23 , merouane15 ] ) . If I is an \alpha -set of a graph G , then for every u\in I either {\rm epn}(u,I)=\emptyset or {\rm epn}(u,I)\neq\emptyset and {\rm epn}(u,I) is a clique. 4 P_{5} -free graphs Our aim in this section is to prove Theorem 5 , that is, we prove that if G is a P_{5} -free graph, then \gamma_{s}(G)\leq\frac{3}{2}\alpha(G) . We note that this bound can be achieved on the disjoint union of C_{5} ’s. Let G be a P_{5} -free graph (possibly disconnected) and I be an \alpha -set of G . By Observation 1 , the set I is a dominating set of G . If |I|=1 , then G is a complete graph and hence I is a secure dominating set of G , and so in this case \gamma_{s}(G)=1=\alpha(G) . If |I|\geq 2 and I is a secure dominating set of G , then we have \gamma_{s}(G)\leq|I|=\alpha(G) . Hence we may assume that |I|\geq 2 and I is not a secure dominating set of G , for otherwise, \gamma_{s}(G)\leq\alpha(G)<\frac{3}{2}\alpha(G) , as desired. We now describe a procedure that we call “SDS- P_{5} -FREE” that builds a secure dominating set S of G starting with the initial \alpha -set I and such that at each stage of the procedure the property that the resulting set, which includes vertices from V(G)\setminus I iteratively to S , is a dominating set of G is preserved. For every iteration of the procedure SDS- P_{5} -FREE, we partition the set S as A_{S}\cup B_{S} as defined in ( P 1 ).