Ask Your Question
1

List of all dominating sets in a graph

asked 2018-01-05 10:24:11 +0100

Deepak Sarma gravatar image

updated 2018-01-05 10:35:32 +0100

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2018-01-05 11:55:25 +0100

vdelecroix gravatar image

updated 2018-01-05 11:55:39 +0100

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.

edit flag offensive delete link more

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 gravatar imageDeepak Sarma ( 2018-01-08 09:17:55 +0100 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-01-05 10:24:11 +0100

Seen: 612 times

Last updated: Jan 05 '18