Secure domination in $P_5$-free graphs

Abstract

A dominating set of a graph $G$ is a set $S\subseteq V(G)$ such that every vertex in $V(G)\setminus S$ has a neighbor in $S$, where two vertices are neighbors if they are adjacent. A secure dominating set of $G$ is a dominating set $S$ of $G$ with the additional property that for every vertex $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 ${\hat{I}}_s^3(G)$, is the minimum cardinality of a secure dominating set of $G$. We prove that if $G$ is a $P_5$-free graph, then ${\hat{I}}_s^3(G)\le \frac{3}{2}\hat{I}\pm (G)$, where $\hat{I}\pm (G)$ denotes the independence number of $G$. We further show that if $G$ is a connected $(P_5,H)$-free graph for some $H\in \{P_3\cup P_1,K_2\cup 2K_1,\text{paw},C_4\}$, then ${\hat{I}}_s^3(G)\le \max \{3,\hat{I}\pm (G)\}$. We also show that if $G$ is a $(P_3\cup P_2)$-free graph, then ${\hat{I}}_s^3(G)\le \hat{I}\pm (G)+1$.