Connected Dominating Sets in Triangulations

Prosenjit Bose, Vida Dujmović, Hussein Houdrouge +2

A dominating set of a graph $G$ is \emph{connected} if it induces a connected graph in $G$. For planar triangulations, it has been known since 1990 that every $n$-vertex triangulat…