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
Thank you very much, Andrew D. King. I also found that it is NP-complete even for planar 4-regular graphs. – Martin Manrique