Domination¶
This module implements methods related to the notion of domination in graphs, and more precisely:
Return a minimum dominating set of the graph. 

Return an iterator over the minimal dominating sets of a graph. 

Check whether a set of vertices dominates a graph. 

Check whether a set of vertices has redundant vertices (with respect to domination). 

Return the private neighbors of a vertex with respect to other vertices. 
EXAMPLES:
We compute the size of a minimum dominating set of the Petersen graph:
sage: g = graphs.PetersenGraph()
sage: g.dominating_set(value_only=True)
3
We enumerate the minimal dominating sets of the 5star graph:
sage: g = graphs.StarGraph(5)
sage: list(g.minimal_dominating_sets())
[{0}, {1, 2, 3, 4, 5}]
Now only those that dominate the middle vertex:
sage: list(g.minimal_dominating_sets([0]))
[{0}, {1}, {2}, {3}, {4}, {5}]
Now the minimal dominating sets of the 5path graph:
sage: g = graphs.PathGraph(5)
sage: list(g.minimal_dominating_sets())
[{0, 2, 4}, {1, 4}, {0, 3}, {1, 3}]
We count the minimal dominating sets of the Petersen graph:
sage: sum(1 for _ in graphs.PetersenGraph().minimal_dominating_sets())
27
Methods¶
 sage.graphs.domination.dominating_set(g, independent, total=False, value_only=False, solver=False, verbose=None, integrality_tolerance=0)¶
Return a minimum dominating set of the graph.
A minimum dominating set \(S\) of a graph \(G\) is a set of its vertices of minimal cardinality such that any vertex of \(G\) is in \(S\) or has one of its neighbors in \(S\). See the Wikipedia article Dominating_set.
As an optimization problem, it can be expressed as:
\[\begin{split}\mbox{Minimize : }&\sum_{v\in G} b_v\\ \mbox{Such that : }&\forall v \in G, b_v+\sum_{(u,v)\in G.edges()} b_u\geq 1\\ &\forall x\in G, b_x\mbox{ is a binary variable}\end{split}\]INPUT:
independent
– boolean (default:False
); whenTrue
, computes a minimum independent dominating set, that is a minimum dominating set that is also an independent set (see alsoindependent_set()
)total
– boolean (default:False
); whenTrue
, computes a total dominating set (see the See the Wikipedia article Dominating_set)value_only
– boolean (default:False
); whether to only return the cardinality of the computed dominating set, or to return its list of vertices (default)solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
EXAMPLES:
A basic illustration on a
PappusGraph
:sage: g = graphs.PappusGraph() sage: g.dominating_set(value_only=True) 5
If we build a graph from two disjoint stars, then link their centers we will find a difference between the cardinality of an independent set and a stable independent set:
sage: g = 2 * graphs.StarGraph(5) sage: g.add_edge(0, 6) sage: len(g.dominating_set()) 2 sage: len(g.dominating_set(independent=True)) 6
The total dominating set of the Petersen graph has cardinality 4:
sage: G = graphs.PetersenGraph() sage: G.dominating_set(total=True, value_only=True) 4
The dominating set is calculated for both the directed and undirected graphs (modification introduced in trac ticket #17905):
sage: g = digraphs.Path(3) sage: g.dominating_set(value_only=True) 2 sage: g = graphs.PathGraph(3) sage: g.dominating_set(value_only=True) 1
 sage.graphs.domination.is_dominating(G, dom, focus=None)¶
Check whether
dom
is a dominating set ofG
.We say that a set \(D\) of vertices of a graph \(G\) dominates a set \(S\) if every vertex of \(S\) either belongs to \(D\) or is adjacent to a vertex of \(D\). Also, \(D\) is a dominating set of \(G\) if it dominates \(V(G)\).
INPUT:
dom
– iterable of vertices ofG
; the vertices of the supposed dominating set.focus
– iterable of vertices ofG
(default:None
); if specified, this method checks instead ifdom
dominates the vertices infocus
.
EXAMPLES:
sage: g = graphs.CycleGraph(5) sage: g.is_dominating([0,1], [4, 2]) True sage: g.is_dominating([0,1]) False
 sage.graphs.domination.is_redundant(G, dom, focus=None)¶
Check whether
dom
has redundant vertices.For a graph \(G\) and sets \(D\) and \(S\) of vertices, we say that a vertex \(v \in D\) is redundant in \(S\) if \(v\) has no private neighbor with respect to \(D\) in \(S\). In other words, there is no vertex in \(S\) that is dominated by \(v\) but not by \(D \setminus \{v\}\).
INPUT:
dom
– iterable of vertices ofG
; where we look for redundant vertices.focus
– iterable of vertices ofG
(default:None
); if specified, this method checks instead whetherdom
has a redundant vertex infocus
.
Warning
The assumption is made that
focus
(if provided) does not contain repeated vertices.EXAMPLES:
sage: G = graphs.CubeGraph(3) sage: G.is_redundant(['000', '101'], ['011']) True sage: G.is_redundant(['000', '101']) False
 sage.graphs.domination.minimal_dominating_sets(G, to_dominate=None, work_on_copy=True)¶
Return an iterator over the minimal dominating sets of a graph.
INPUT:
G
– a graph.to_dominate
– vertex iterable orNone
(default:None
); the set of vertices to be dominated.work_on_copy
– boolean (default:True
); whether or not to work on a copy of the input graph; if set toFalse
, the input graph will be modified (relabeled).
OUTPUT:
An iterator over the inclusionminimal sets of vertices of
G
. Ifto_dominate
is provided, return an iterator over the inclusionminimal sets of vertices that dominate the vertices ofto_dominate
.ALGORITHM: The algorithm described in [BDHPR2019].
AUTHOR: JeanFlorent Raymond (20190304) – initial version.
EXAMPLES:
sage: G = graphs.ButterflyGraph() sage: ll = list(G.minimal_dominating_sets()) sage: pp = [{0, 1}, {1, 3}, {0, 2}, {2, 3}, {4}] sage: len(ll) == len(pp) and all(x in pp for x in ll) and all(x in ll for x in pp) True sage: ll = list(G.minimal_dominating_sets([0,3])) sage: pp = [{0}, {3}, {4}] sage: len(ll) == len(pp) and all(x in pp for x in ll) and all(x in ll for x in pp) True sage: ll = list(G.minimal_dominating_sets([4])) sage: pp = [{4}, {0}, {1}, {2}, {3}] sage: len(ll) == len(pp) and all(x in pp for x in ll) and all(x in ll for x in pp) True
sage: ll = list(graphs.PetersenGraph().minimal_dominating_sets()) sage: pp = [{0, 2, 6}, ....: {0, 9, 3}, ....: {0, 8, 7}, ....: {1, 3, 7}, ....: {1, 4, 5}, ....: {8, 1, 9}, ....: {8, 2, 4}, ....: {9, 2, 5}, ....: {3, 5, 6}, ....: {4, 6, 7}, ....: {0, 8, 2, 9}, ....: {0, 3, 6, 7}, ....: {1, 3, 5, 9}, ....: {8, 1, 4, 7}, ....: {2, 4, 5, 6}, ....: {0, 1, 2, 3, 4}, ....: {0, 1, 2, 5, 7}, ....: {0, 1, 4, 6, 9}, ....: {0, 1, 5, 6, 8}, ....: {0, 8, 3, 4, 5}, ....: {0, 9, 4, 5, 7}, ....: {8, 1, 2, 3, 6}, ....: {1, 2, 9, 6, 7}, ....: {9, 2, 3, 4, 7}, ....: {8, 2, 3, 5, 7}, ....: {8, 9, 3, 4, 6}, ....: {8, 9, 5, 6, 7}] sage: len(ll) == len(pp) and all(x in pp for x in ll) and all(x in ll for x in pp) True
 sage.graphs.domination.private_neighbors(G, vertex, dom)¶
Return the private neighbors of a vertex with respect to other vertices.
A private neighbor of a vertex \(v\) with respect to a vertex subset \(D\) is a closed neighbor of \(v\) that is not dominated by a vertex of \(D \setminus \{v\}\).
INPUT:
vertex
– a vertex ofG
.dom
– iterable of vertices ofG
; the vertices possibly stealing private neighbors fromvertex
.
OUTPUT:
Return the closed neighbors of
vertex
that are not closed neighbors of any other vertex ofdom
.EXAMPLES:
sage: g = graphs.PathGraph(5) sage: list(g.private_neighbors(1, [1, 3, 4])) [1, 0] sage: list(g.private_neighbors(1, [3, 4])) [1, 0] sage: list(g.private_neighbors(1, [3, 4, 0])) []