Generalized domination in degenerate graphs: A complete dichotomy of computational complexity

Abstract

We show that for every k, the problem of existence of a (sigma,rho)-dominating set performs a complete dichotomy when restricted to k-degenerate graphs, and we fully characterize the polynomial and NP-complete instances. It is further shown that the problem is polynomial time solvable if sigma, rho are such that every k-degenerate graph contains at most one (sigma, rho)-dominating set, and NP-complete otherwise.

This relates to the concept of ambivalent graphs previously introduced for chordal graphs.

Keywords

• Generalized
• domination
• degenerate
• graphs
• complete
• dichotomy
• computational
• complexity