1
$\begingroup$

Hi,

I believe it is just an easy question, but I have not found the answer: Is the optimization / decision problem DOMINATING SET NP-complete when restricted to regular graphs? Where can I find a proof of that?

Thank you, MO users.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Dominating set is NP-complete, and even APX-complete, for cubic graphs. dx.doi.org/10.1016/S0304-3975(98)00158-3 $\endgroup$
    – Andrew D. King
    Commented Feb 7, 2013 at 18:32
  • $\begingroup$ Thank you very much, Andrew D. King. I also found that it is NP-complete even for planar 4-regular graphs. $\endgroup$
    – Martin Manrique
    Commented Feb 10, 2013 at 15:55

1 Answer 1

Reset to default
3
$\begingroup$

Dominating set is NP-complete, and even APX-complete, for cubic graphs. dx.doi.org/10.1016/S0304-3975(98)00158-3 – Andrew D. King

Thank you very much, Andrew D. King. I also found that it is NP-complete even for planar 4-regular graphs. – Martin Manrique

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .