A Lower bound for Secure Domination Number of an Outerplanar Graph

Abstract

A subset $S$ of vertices in a graph $G$ is a secure dominating set of $G$ if $S$ is a dominating set of $G$ and, for each vertex $u\notin S$, there is a vertex $v\in S$ such that $uv$ is an edge and $(S\setminus \{v\})\cup \{u\}$ is also a dominating set of $G$. The secure domination number of $G$, denoted by ${\gamma }_s(G)$, is the cardinality of a smallest secure dominating sets of $G$. In this paper, we prove that for any outerplanar graph with $n\ge 4$ vertices, ${\gamma }_s(G)\ge (n+4)/5$ and the bound is tight.

7 pages, 1 figure. arXiv admin note: text overlap with arXiv:2403.03404