The term of the concept to find the minimum vertex cover which covers all of the vertices (not edges) of an undirected graph only once

graph theorypattern matchingterminology

I am actually looking for a term, I have googled for like past couple of hours and I had no luck so far.

So there exists a thing called, minimum vertex cover which implies " a set of vertices such that each edge of the graph is incident to at least one vertex of the set".

I'm looking for a similar concept only slightly different to the original, it is to find a set of vertices such that the set covers all of the vertices in a graph regardless of each edge is covered or not without any duplicates

For example:

Graph: iamge

Solution: image2

So the solution isn't a minimum vertex cover since all edges aren't covered, however the set of vertices do cover every other vertex in the graph without any overlaps/duplicates.


Edit credits to angryavian for a more concise question of my initial query:

Phrased another way: you want a minimal subset of vertices S such that the union of their neighborhoods is all the vertices, and moreover the union is a disjoint union?

Best Answer

A set of vertices whose (closed) neighborhoods partition $V(G)$ is called a perfect code (sometimes also an efficient dominating set). See for example Chapter 4 in this book.

The term was first introduced here, extending the notion of perfect codes from coding theory. In general a perfect $d$-code in a metric space is a covering with disjoint balls of radius $d$. In graphs the metric is just the usual distance, so balls of radius 1 are the same as neighborhoods $N[v]$ of vertices. In coding theory the vertices would correspond to words and the distance is for example Hamming distance; the idea is that if you select a vertex in the perfect code, then even after making one step in error, you will always be able to recover it (in a unique way).

Perfect codes are always independent sets (no two elements are adjacent) and dominating sets (their neighborhoods cover everything). Deciding whether any perfect code exists in a given graph is NP-hard, even in planar graphs (Theorem 4.4 in the book). If there is one, then all perfect codes have the same size (Theorem 4.2).

However, note that in the Lights Out puzzle you cite you don't actually need a perfect code. You need a set of vertices $S$ such that every vertex is included in $N[v]$ for $v \in S$ an odd number of times (instead of exactly once). The condition can be phrased as a system of linear equations over $\mathbb{Z}_2$, which can be solved in polynomial time! See for example here.

Related Question