On the complexity of Dominating Set for graphs with fixed diameter
share
A set S⊆ V of a graph G=(V,E) is a dominating set if each vertex has a neighbor in S or belongs to S. Dominating Set is the problem of deciding, given a graph G and an integer k≥ 1, if G has a dominating set of size at most k. It is well known that this problem is 𝖭𝖯-complete even for claw-free graphs. We give a complexity dichotomy for Dominating Set for the class of claw-free graphs with diameter d. We show that the problem is 𝖭𝖯-complete for every fixed d≥ 3 and polynomial time solvable for d≤ 2. To prove the case d=2, we show that Minimum Maximal Matching can be solved in polynomial time for 2K_2-free graphs.
READ FULL TEXT