Autor:	Spacapan, Simon
Rok vydání:	2018
Předmět:	Mathematics - Combinatorics 05C10 05C69
Druh dokumentu:	Working Paper
Popis:	We introduce a class of plane graphs called weak near-triangulations, and prove that this class is closed under certain graph operations. Then we use the properties of weak near-triangulations to prove that every plane triangulation on $n>6$ vertices has a dominating set of size at most $17n/53$. This improves the bound $n/3$ obtained by Matheson and Tarjan.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1806.06932 Zobrazit plný text záznamu View this record from Arxiv