Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2011.04255 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914787903930368 |
|---|---|
| author | Claverol, M. García, A. Hernández, G. Hernando, C. Maureso, M. Mora, M. Tejel, J. |
| author_facet | Claverol, M. García, A. Hernández, G. Hernando, C. Maureso, M. Mora, M. Tejel, J. |
| contents | A total dominating set of a graph $G=(V,E)$ is a subset $D$ of $V$ such that every vertex in $V$ is adjacent to at least one vertex in $D$. The total domination number of $G$, denoted by $γ_t (G)$, is the minimum cardinality of a total dominating set of $G$. A near-triangulation is a biconnected planar graph that admits a plane embedding such that all of its faces are triangles except possibly the outer face. We show in this paper that $γ_t (G) \le \lfloor \frac{2n}{5}\rfloor$ for any near-triangulation $G$ of order $n\ge 5$, with two exceptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2011_04255 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Total domination in plane triangulations Claverol, M. García, A. Hernández, G. Hernando, C. Maureso, M. Mora, M. Tejel, J. Combinatorics Computational Geometry A total dominating set of a graph $G=(V,E)$ is a subset $D$ of $V$ such that every vertex in $V$ is adjacent to at least one vertex in $D$. The total domination number of $G$, denoted by $γ_t (G)$, is the minimum cardinality of a total dominating set of $G$. A near-triangulation is a biconnected planar graph that admits a plane embedding such that all of its faces are triangles except possibly the outer face. We show in this paper that $γ_t (G) \le \lfloor \frac{2n}{5}\rfloor$ for any near-triangulation $G$ of order $n\ge 5$, with two exceptions. |
| title | Total domination in plane triangulations |
| topic | Combinatorics Computational Geometry |
| url | https://arxiv.org/abs/2011.04255 |