2018/06/18 by Spacapan, Simon · 1 citation
#05C10 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1806.06932
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.