Secure Total Domination Number in Maximal Outerplanar Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910403079962624 |
|---|---|
| author | Aita, Yasufumi Araki, Toru |
| author_facet | Aita, Yasufumi Araki, Toru |
| contents | A subset $S$ of vertices in a graph $G$ is a secure total dominating set of $G$ if $S$ is a total 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 total dominating set of $G$. We show that if $G$ is a maximal outerplanar graph of order $n$, then $G$ has a total secure dominating set of size at most $\lfloor 2n/3 \rfloor$. Moreover, if an outerplanar graph $G$ of order $n$, then each secure total dominating set has at least $\lceil (n+2)/3 \rceil$ vertices. We show that these bounds are best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_03404 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Secure Total Domination Number in Maximal Outerplanar Graphs Aita, Yasufumi Araki, Toru Combinatorics Discrete Mathematics 05C69, 05C10 G.2.2 A subset $S$ of vertices in a graph $G$ is a secure total dominating set of $G$ if $S$ is a total 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 total dominating set of $G$. We show that if $G$ is a maximal outerplanar graph of order $n$, then $G$ has a total secure dominating set of size at most $\lfloor 2n/3 \rfloor$. Moreover, if an outerplanar graph $G$ of order $n$, then each secure total dominating set has at least $\lceil (n+2)/3 \rceil$ vertices. We show that these bounds are best possible. |
| title | Secure Total Domination Number in Maximal Outerplanar Graphs |
| topic | Combinatorics Discrete Mathematics 05C69, 05C10 G.2.2 |
| url | https://arxiv.org/abs/2403.03404 |