The efficiency of AC graphs (Q686253)

If \(G=(V,e)\) is an undirected graph with a distinguished subset \(R \subset V\), then a vertex \(v \in V \backslash R\) is said to be dominated by \(s \in R\), if \(v\) and \(s\) are connected by an edge. The maximum efficiency \(\varepsilon(G)\) is the maximum number of vertices in \(V \backslash R\) over all subsets \(R \subset V\) that are dominated by exactly one node in \(R\). Expanding a result of \textit{P. J. Bernhard}, \textit{S. T. Hedetniemi} and \textit{D. P. Jacobs} [ibid. 44, 99-108 (1993; Zbl 0780.68097)], the present author constructs a linear time algorithm for computing \(\varepsilon(G)\) when \(G\) is an \(AC\) graph.