In Graph theory, a minimum vertex cover is the smallest set of vertices that covers all edges.

Minimum Vertex Cover

In this diagram, the minimum Vertex cover would require both 3 and either 1 or 2 (to cover the edge between 1 and 2).

Is there an equivalent set of minimum vertex required to connect at least once to all other vertices. Limited Minimum Vertex

In this diagram, only 3 would be required, as it connects to edges that connect to all other Vertices.


The set of vertices you are looking for is called a dominating set and the size of the smallest dominating set is the dominating number of the graph. These have been extensively researched and a quick Google search will yield plenty of hits.


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.