pith. sign in

arxiv: 1806.06932 · v1 · pith:65Q37H2Wnew · submitted 2018-06-18 · 🧮 math.CO

The domination number of plane triangulations

classification 🧮 math.CO
keywords planeclassnear-triangulationsproveweakboundcalledcertain
0
0 comments X
read the original 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 $17n/53$. This improves the bound $n/3$ obtained by Matheson and Tarjan.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.