Connected Dominating Sets in Triangulations

Prosenjit Bose, Vida Dujmović, Hussein Houdrouge +2

We show that every $n$-vertex triangulation has a connected dominating set of size at most $10n/21$. Equivalently, every $n$ vertex triangulation has a spanning tree with at least…