The domination number of plane triangulations
2019
Abstract 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 17 n / 53 . This improves the bound n / 3 obtained by Matheson and Tarjan.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
5
Citations
NaN
KQI