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.

answered 7 years ago

vdelecroix
7655 ●20 ●85 ●168 http://www.labri.fr/pe...

updated 7 years ago

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.

link

Comments

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?

Deepak Sarma ( 7 years ago )

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

List of all dominating sets in a graph

G.dominating_set()

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

List of all dominating sets in a graph savecancel

G.dominating_set()

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

List of all dominating sets in a graph