Maximal Independent Sets in Planar Triangulations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929566762663936 |
|---|---|
| author | Francis, P. Illickan, Abraham M. Jose, Lijo M. Rajendraprasad, Deepak |
| author_facet | Francis, P. Illickan, Abraham M. Jose, Lijo M. Rajendraprasad, Deepak |
| contents | We show that every planar triangulation on $n$ vertices has a maximal independent set of size at most $n/3$. This affirms a conjecture by Botler, Fernandes and Gutiérrez [Electron.\ J.\ Comb., 2024], which in turn would follow if an open question of Goddard and Henning [Appl.\ Math.\ Comput., 2020] which asks if every planar triangulation has three disjoint maximal independent sets were answered in the affirmative. Since a maximal independent set is a special type of dominating set (independent dominating set), this is a structural strengthening of a major result by Matheson and Tarjan [Eur.\ J.\ Comb., 1996] that every triangulated disc has a dominating set of size at most $n/3$, but restricted to triangulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21808 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Maximal Independent Sets in Planar Triangulations Francis, P. Illickan, Abraham M. Jose, Lijo M. Rajendraprasad, Deepak Combinatorics Discrete Mathematics We show that every planar triangulation on $n$ vertices has a maximal independent set of size at most $n/3$. This affirms a conjecture by Botler, Fernandes and Gutiérrez [Electron.\ J.\ Comb., 2024], which in turn would follow if an open question of Goddard and Henning [Appl.\ Math.\ Comput., 2020] which asks if every planar triangulation has three disjoint maximal independent sets were answered in the affirmative. Since a maximal independent set is a special type of dominating set (independent dominating set), this is a structural strengthening of a major result by Matheson and Tarjan [Eur.\ J.\ Comb., 1996] that every triangulated disc has a dominating set of size at most $n/3$, but restricted to triangulations. |
| title | Maximal Independent Sets in Planar Triangulations |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2410.21808 |