Complementary acyclic domination in graphs
B. Janakiram, N. D. Soner, Matthew A. Davis · 2004
Review : Given a graph G=(V,E), a vertex set D⊆V is a complementary acyclic dominating set if every vertex in V∖D is adjacent to a vertex in D and the subgraph induced by V∖D is acyclic. The complementary acyclic domination number γca(G) is the size of the smallest complementary acyclic dominating set of G. In the paper, relations are established between γca(G) and the size of the smallest vertex cover, the smallest acyclic dominating set, the smallest connected dominating set, the smallest dominating tree, and the chromatic number. The authors suggest that there is an application of this type of dominating set to the problem of placing traffic signals in a road network to minimize accidents. In the reviewer's opinion, the attempt to relate this to a real-life application is a bit of a stretch.