Domination

This module implements methods related to the notion of domination in graphs, and more precisely:

dominating_set()

Return a minimum dominating set of the graph.

minimal_dominating_sets()

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

is_dominating()

Check whether a set of vertices dominates a graph.

is_redundant()

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

private_neighbors()

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 5-star 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 5-path 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=False, total=False, value_only=False, solver=None, verbose=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); when True, computes a minimum independent dominating set, that is a minimum dominating set that is also an independent set (see also independent_set())

  • total – boolean (default: False); when True, 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 – (default: None); specifies a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

  • verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

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 of G.

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 of G; the vertices of the supposed dominating set.

  • focus – iterable of vertices of G (default: None); if specified, this method checks instead if dom dominates the vertices in focus.

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 of G; where we look for redundant vertices.

  • focus – iterable of vertices of G (default: None); if specified, this method checks instead whether dom has a redundant vertex in focus.

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 or None (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 to False, the input graph will be modified (relabeled).

OUTPUT:

An iterator over the inclusion-minimal sets of vertices of G. If to_dominate is provided, return an iterator over the inclusion-minimal sets of vertices that dominate the vertices of to_dominate.

ALGORITHM: The algorithm described in [BDHPR2019].

AUTHOR: Jean-Florent Raymond (2019-03-04) – 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 of G.

  • dom – iterable of vertices of G; the vertices possibly stealing private neighbors from vertex.

OUTPUT:

Return the closed neighbors of vertex that are not closed neighbors of any other vertex of dom.

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]))
[]