Loading [MathJax]/jax/output/HTML-CSS/jax.js
Ask Your Question
1

List of all dominating sets in a graph

asked 7 years ago

Deepak Sarma gravatar image

updated 7 years ago

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 Dc(complement of D) is independent.

Preview: (hide)

1 Answer

Sort by » oldest newest most voted
1

answered 7 years ago

vdelecroix gravatar image

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.

Preview: (hide)
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 gravatar imageDeepak Sarma ( 7 years ago )

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: 7 years ago

Seen: 636 times

Last updated: Jan 05 '18