A Lower bound for Secure Domination Number of an Outerplanar Graph
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910364705226752 |
|---|---|
| author | Araki, Toru |
| author_facet | Araki, Toru |
| contents | 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 \not\in 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 $γ_{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 \geq 4$ vertices, $γ_{s}(G) \geq (n+4)/5$ and the bound is tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_06493 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Lower bound for Secure Domination Number of an Outerplanar Graph Araki, Toru Combinatorics Discrete Mathematics 05C69, 05C10 G.2.2 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 \not\in 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 $γ_{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 \geq 4$ vertices, $γ_{s}(G) \geq (n+4)/5$ and the bound is tight. |
| title | A Lower bound for Secure Domination Number of an Outerplanar Graph |
| topic | Combinatorics Discrete Mathematics 05C69, 05C10 G.2.2 |
| url | https://arxiv.org/abs/2403.06493 |