Domination#

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

dominating_set()

Return a minimum distance-\(k\) 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.

greedy_dominating_set()

Return a greedy distance-\(k\) dominating set of the graph.

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, k, independent=1, total=False, value_only=False, solver=False, verbose=None, integrality_tolerance=0)#

Return a minimum distance-\(k\) 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.

A minimum distance-\(k\) dominating set is a set \(S\) of vertices of \(G\) of minimal cardinality such that any vertex of \(G\) is in \(S\) or at distance at most \(k\) from a vertex in \(S\). A distance-\(0\) dominating set is the set of vertices itself, and when \(k\) is the radius of the graph, any vertex dominates all the other vertices.

As an optimization problem, it can be expressed as follows, where \(N^k(u)\) denotes the set of vertices at distance at most \(k\) from \(u\) (the set of neighbors when \(k=1\)):

\[\begin{split}\mbox{Minimize : }&\sum_{v\in G} b_v\\ \mbox{Such that : }&\forall v \in G, b_v+\sum_{u \in N^k(v)} b_u\geq 1\\ &\forall x\in G, b_x\mbox{ is a binary variable}\end{split}\]

INPUT:

  • k – a non-negative integer (default: 1); the domination distance

  • 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 – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP 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.

  • integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.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

Cardinality of distance-\(k\) dominating sets:

sage: G = graphs.PetersenGraph()
sage: [G.dominating_set(k=k, value_only=True) for k in range(G.radius() + 1)]
[10, 3, 1]
sage: G = graphs.PathGraph(5)
sage: [G.dominating_set(k=k, value_only=True) for k in range(G.radius() + 1)]
[5, 2, 1]
sage.graphs.domination.greedy_dominating_set(G, k=1, vertices=None, ordering=None, return_sets=False, closest=False)#

Return a greedy distance-\(k\) dominating set of the graph.

A distance-\(k\) 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 is at distance at most \(k\) from a vertex in \(S\). See the Wikipedia article Dominating_set.

When \(G\) is directed, vertex \(u\) can be a dominator of vertex \(v\) if there is a directed path of length at most \(k\) from \(u\) to \(v\).

This method implements a greedy heuristic to find a minimal dominatic set.

INPUT:

  • G – a Graph

  • k – integer (default: 1); the domination distance to consider

  • vertices – iterable container of vertices (default: None); when specified, return a dominating set of the specified vertices only

  • ordering – string (default: None); specify the order in which to consider the vertices

    • None – if vertices is None, then consider the vertices in the order given by list(G). Otherwise, consider the vertices in the order of iteration of vertices.

    • "degree_min" – consider the vertices by increasing degree

    • "degree_max" – consider the vertices by decreasing degree

  • return_sets – boolean (default: False); whether to return the vertices of the dominating set only (default), or a dictionary mapping each vertex of the dominating set to the set of vertices it dominates.

  • closest – boolean (default: False); whether to attach a vertex to its closest dominator or not. This parameter is use only when return_sets is True.

EXAMPLES:

Dominating sets of a path:

sage: from sage.graphs.domination import greedy_dominating_set
sage: G = graphs.PathGraph(5)
sage: sorted(greedy_dominating_set(G, ordering=None))
[0, 2, 4]
sage: sorted(greedy_dominating_set(G, ordering="degree_min"))
[0, 2, 4]
sage: sorted(greedy_dominating_set(G, ordering="degree_max"))
[1, 3]
sage: sorted(greedy_dominating_set(G, k=2, ordering=None))
[0, 3]
sage: sorted(greedy_dominating_set(G, k=2, ordering="degree_min"))
[0, 4]
sage: sorted(greedy_dominating_set(G, k=2, ordering="degree_max"))
[1, 4]
sage: greedy_dominating_set(G, k=3, ordering="degree_min", return_sets=True, closest=False)
{0: {0, 1, 2, 3}, 4: {4}}
sage: greedy_dominating_set(G, k=3, ordering="degree_min", return_sets=True, closest=True)
{0: {0, 2, 3}, 4: {1, 4}}

Asking for a dominating set of a subset of vertices:

sage: from sage.graphs.domination import greedy_dominating_set
sage: from sage.graphs.domination import is_dominating
sage: G = graphs.PetersenGraph()
sage: vertices = {0, 1, 2, 3, 4, 5}
sage: dom = greedy_dominating_set(G, vertices=vertices, return_sets=True)
sage: sorted(dom)
[0, 2]
sage: is_dominating(G, dom, focus=vertices)
True
sage: is_dominating(G, dom)
False
sage: dominated = [u for v in dom for u in dom[v]]
sage: sorted(dominated) == sorted(vertices)
True

Influence of the ordering of the vertices on the result:

sage: from sage.graphs.domination import greedy_dominating_set
sage: G = graphs.StarGraph(4)
sage: greedy_dominating_set(G, vertices=[0, 1, 2, 3, 4])
[0]
sage: sorted(greedy_dominating_set(G, vertices=[1, 2, 3, 4, 0]))
[1, 2, 3, 4]

Dominating set of a directed graph:

sage: from sage.graphs.domination import greedy_dominating_set
sage: D = digraphs.Path(3)
sage: sorted(greedy_dominating_set(D, vertices=[0, 1, 2]))
[0, 2]
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]))
[]