Efficient Dominating Sets in Spanning Trees

Abstract

An efficient dominating set $S$ for a graph $G$ is a set of vertices such that every vertex in $G$ is in the closed neighborhood of exactly one vertex in $S$. If $G$ is connected and has no vertices of degree one, then $G$ has a spanning tree which has an efficient dominating set. An $O(n)$ algorithm for finding such a spanning tree and its efficient dominating set is given.