ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 08 Jan 2018 09:17:55 +0100List of all dominating sets in a graphhttps://ask.sagemath.org/question/40468/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.Fri, 05 Jan 2018 10:24:11 +0100https://ask.sagemath.org/question/40468/list-of-all-dominating-sets-in-a-graph/Answer by vdelecroix for <p>The inbuilt function in sage for dominating set of a graph $G$ is</p>
<h1>G.dominating_set()</h1>
<p>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.</p>
https://ask.sagemath.org/question/40468/list-of-all-dominating-sets-in-a-graph/?answer=40469#post-id-40469There 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.Fri, 05 Jan 2018 11:55:25 +0100https://ask.sagemath.org/question/40468/list-of-all-dominating-sets-in-a-graph/?answer=40469#post-id-40469Comment by Deepak Sarma for <p>There is the object <code>IndependentSets</code> in <code>sage.graphs.independent_sets</code> that can help you (as the complement of an independent set is a vertex cover).</p>
<pre><code>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])
</code></pre>
<p>To add further restriction, you can just filter. If it is not efficient enough, you will have to implement your own backtracker.</p>
https://ask.sagemath.org/question/40468/list-of-all-dominating-sets-in-a-graph/?comment=40530#post-id-40530Thank 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?Mon, 08 Jan 2018 09:17:55 +0100https://ask.sagemath.org/question/40468/list-of-all-dominating-sets-in-a-graph/?comment=40530#post-id-40530