# complexity of dominating sets of regular graphs

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.

-
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 Feb 7 '13 at 18:32
Thank you very much, Andrew D. King. I also found that it is NP-complete even for planar 4-regular graphs. –  Martin Manrique Feb 10 '13 at 15:55

## 1 Answer

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

-