# List of all dominating sets in a graph

The inbuilt function in sage for dominating set of a graph $G$ is

# G.dominating_set()

But this gives only a minimum dominating set of the graph. What I want is the list of all dominating sets of the graph. How to get this? Besides in the inbuilt function we have some additional options, like dominating_set(independent=True) which gives a minimum independent dominating set of the graph. Now if I want a minimum dominating set with some other properties, how to set it? For example if I need a minimal dominating set D so that $D^c$(complement of D) is independent.

edit retag close merge delete

Sort by » oldest newest most voted

There is the object IndependentSets in sage.graphs.independent_sets that can help you (as the complement of an independent set is a vertex cover).

sage: from sage.graphs.independent_sets import IndependentSets
sage: G = graphs.PetersenGraph()
sage: V = set(G.vertices())
sage: for I in IndependentSets(G, maximal=True):
....:     print(V.difference(I))
set([1, 3, 4, 5, 7, 8, 9])
set([1, 3, 4, 5, 6, 7])
set([1, 2, 4, 5, 8, 9])
...
set([0, 1, 2, 4, 7, 8, 9])
set([0, 1, 2, 3, 5, 8, 9])


To add further restriction, you can just filter. If it is not efficient enough, you will have to implement your own backtracker.

more

Thank you for your answer. But complement of an independent set is a vertex cover only for connected graph. How to include disconnected graphs here? And what about the first question, how to obtain all the dominating sets?

( 2018-01-08 09:17:55 +0100 )edit