I apologize for a (probably) trivial question but I am looking for a problem name so i can google for its potential solutions. The problem is: Unlike in minimum vertex cover problem where the goal is to compute a set of vertices covering all the edges in a given graph, I am looking for a version where the goal is to compute the minimum number of vertices such that the union of their adjacent neighbours (including the computed ones) cover the entire set of vertices of a given graph.

for example if a triangle is chosen as an example then minimum vertex cover would be two and for the above described instance of the problem it would be one.

Am I succeeding in making any sense?

thank you


The key phrase is "dominating set".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.