Add utility functions for checking whether a vertex subset is dominating
Domination is one of the most central concepts in (algorithmic) graph theory, but there's not a lot of support for domination in IGraphM. As a start, to extend the family consisting of IGDominatorTree and IGImmediateDominators, I'd suggest adding utility functions to verify whether a given subset of vertices form a dominating set.
To check if S is a dominating set in G, we can check if S intersects the neighborhood of each vertex not in S. In Mathematica, one could write this as:
DominatingSetQ[g_, s_] :=
!MemberQ[Intersection[s, AdjacencyList[g, #]]&/@Complement[VertexList[g], s], {}];
It also not at all common to be interested in connected dominating sets, for which a similar check could then by constructed as:
ConnectedDominatingSetQ[g_, s_] :=
ConnectedGraphQ[Subgraph[g, s]] && DominatingSetQ[g, s];
Ultimately, I think it would be great if IGraphM also had functionality to find a minimum (connected) dominating set, the (connected) domination number and so on, but I think this should be a fine addition and a good start. At the very least, it makes it very easy for the user to write a brute-force algorithm for either problem applicable for tiny graphs.
Do you think adding these functions would make sense?
These are all good suggestions. Thanks! I'll also make a few changes to make it easier to get started with development, and will send you an email during next week.