More results on the complexity of domination problems in graphs

摘要

Given a graph G = (V,E) and an integer r ≥ 1, we call 'r-dominating code' any subset C of V such that every vertex in V is at distance at most T from at least one vertex in C. We investigate and locate in the complexity classes of the polynomial hierarchy, several problems linked with domination in graphs, such as, given r and G, the existence of, or search for, optimal r-dominating codes in G, or optimal r-dominating codes in G containing a subset of vertices X ⊂ V.