domination

Domination

graphcalc.graphs.invariants.domination.complement_is_connected(G: Graph, S: Set[Hashable] | List[Hashable]) → bool[source]

Checks if the complement of a set \(S\) in the graph \(G\) induces a connected subgraph.

The complement of \(S\) is defined as the set of all nodes in \(G\) that are not in \(S\). This function verifies whether the subgraph induced by the complement of \(S\) is connected.

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • S (set) – A subset of nodes in the graph.

Returns:

True if the subgraph induced by the complement of S is connected, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> S = {0}
>>> gc.complement_is_connected(G, S)
True

>>> S = {0, 2}
>>> gc.complement_is_connected(G, S)
False
graphcalc.graphs.invariants.domination.connected_domination_number(G: Graph, **solver_kwargs) → int[source]

Return the connected domination number \(\gamma_c(G)\).

The connected domination number is the minimum size of a connected dominating set:

\[\gamma_c(G) = \min\{ |S| : S \subseteq V(G),\ S \text{ dominates } G,\ \text{and } G[S]\text{ is connected}\}.\]

This wraps minimum_connected_dominating_set().

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • verbose (bool, default=False)

  • solver (str or dict or pulp.LpSolver or type or callable or None, optional)

  • solver_options (dict, optional) – Forwarded to minimum_connected_dominating_set().

Returns:

The connected domination number \(\gamma_c(G)\).

Return type:

int

Raises:

ValueError – If \(G\) is disconnected and nonempty.

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph, cycle_graph
>>> gc.connected_domination_number(path_graph(3))
1
>>> gc.connected_domination_number(path_graph(4))
2
>>> gc.connected_domination_number(cycle_graph(6))
4
graphcalc.graphs.invariants.domination.domination_number(G: Graph, *, verbose: bool = False, solve=None) → int[source]

Calculates the domination number of the graph \(G\).

The domination number is the size of the smallest dominating set in \(G\). It represents the minimum number of nodes required such that every node in the graph is either in the dominating set or adjacent to a node in the set.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

The domination number of G.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.domination_number(G)
2
graphcalc.graphs.invariants.domination.double_roman_domination_number(graph: Graph, **solver_kwargs) → int[source]

Return the double Roman domination number \(\gamma_{dR}(G)\).

Parameters:

  • graph (networkx.Graph or graphcalc.SimpleGraph) – Undirected input graph.

  • verbose (bool, default=False)

  • solver (str or dict or pulp.LpSolver or type or callable or None, optional)

  • solver_options (dict, optional) – Forwarded to minimum_double_roman_dominating_function().

Returns:

\(\gamma_{dR}(G)\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> gc.double_roman_domination_number(path_graph(4))
5
graphcalc.graphs.invariants.domination.independent_domination_number(G: Graph, **solver_kwargs) → int[source]

Return the independent domination number of \(G\).

An independent dominating set is a dominating set that is also an independent set. This wraps minimum_independent_dominating_set().

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • verbose (bool, default=False)

  • solver (str or dict or pulp.LpSolver or type or callable or None, optional)

  • solver_options (dict, optional) – Forwarded to minimum_independent_dominating_set().

Returns:

The independent domination number of \(G\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> gc.independent_domination_number(path_graph(4))
2
graphcalc.graphs.invariants.domination.is_dominating_set(G: Graph, S: Set[Hashable] | List[Hashable]) → bool[source]

Checks if a given set of nodes, \(S\subseteq V\), is a dominating set in the graph \(G\).

A dominating set of a graph \(G = (V, E)\) is a subset of nodes \(S \subseteq V\) such that every node in \(V\) is either in \(S\) or adjacent to a node in \(S\). In other words, every node in the graph is either part of the dominating set or is “dominated” by a node in the dominating set.

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • S (set) – A subset of nodes in the graph to check for domination.

Returns:

True if \(S\) is a dominating set, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> S = {0, 2}
>>> print(gc.is_dominating_set(G, S))
True

>>> S = {0}
>>> print(gc.is_dominating_set(G, S))
False
graphcalc.graphs.invariants.domination.is_outer_connected_dominating_set(G: Graph, S: Set[Hashable] | List[Hashable]) → bool[source]

Checks if a given set \(S\) is an outer-connected dominating set in the graph \(G\).

An outer-connected dominating set \(S \subseteq V\) of a graph \(G = (V, E)\) is a dominating set such that the subgraph induced by the complement of \(S\) is connected.

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • S (set) – A subset of nodes in the graph.

Returns:

True if S is an outer-connected dominating set, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> S = {0, 2, 4}
>>> gc.is_outer_connected_dominating_set(G, S)
False

>>> S = {0, 1, 2}
>>> gc.is_outer_connected_dominating_set(G, S)
True
graphcalc.graphs.invariants.domination.min_maximal_matching_number(G: Graph) → int[source]

Calculates the minimum maximal matching number of the graph G.

The minimum maximal matching number of G is the size of a minimum maximal matching in G. This is equivalent to finding the domination number of the line graph of G.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

The minimum maximal matching number of G.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.min_maximal_matching_number(G)
1
graphcalc.graphs.invariants.domination.minimum_connected_dominating_set(G: Graph, *, verbose: bool = False, solve=None) → Set[Hashable][source]

Find a minimum connected dominating set of \(G\) via integer programming.

A connected dominating set is a set \(S \subseteq V(G)\) such that:

  • (Dominating) every vertex is in \(S\) or adjacent to a vertex in \(S\).

  • (Connected) the induced subgraph \(G[S]\) is connected.

Let \(x_v \in \{0,1\}\) indicate whether \(v\) is selected. Domination is enforced by

\[\sum_{u \in N[v]} x_u \ge 1 \quad \forall v \in V,\]

where \(N[v]\) is the closed neighborhood of \(v\).

Connectivity is enforced with a single-commodity flow formulation that chooses a root among the selected vertices and sends one unit of flow to each other selected vertex.

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • verbose (bool, default=False) – If True, print solver output (when supported).

Notes

Accepts the standard solver kwargs from graphcalc.solvers.with_solver() (e.g., solver="highs" or solver={"name":"GUROBI_CMD","options":{...}}).

Conventions

  • If \(|V(G)|=0\), returns the empty set.

  • If \(G\) is disconnected and nonempty, no connected dominating set exists and this function raises ValueError.

returns:

A minimum connected dominating set.

rtype:

set of hashable

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph, cycle_graph
>>> len(gc.minimum_connected_dominating_set(path_graph(4)))
2
>>> len(gc.minimum_connected_dominating_set(cycle_graph(6)))
4
graphcalc.graphs.invariants.domination.minimum_dominating_set(G: Graph, *, verbose: bool = False, solve=None) → Set[Hashable][source]

Find a minimum dominating set of \(G\) via integer programming.

Let \(x_v \in \{0,1\}\) indicate whether \(v\) is chosen. We solve:

\[\min \sum_{v \in V} x_v \quad \text{s.t. } \sum_{u \in N[v]} x_u \ge 1 \;\; \forall v\in V,\]

where \(N[v]\) is the closed neighborhood of \(v\).

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • verbose (bool, default=False) – If True, print solver output (when supported).

Notes

Accepts the standard solver kwargs from graphcalc.solvers.with_solver() (e.g., solver="highs" or solver={"name":"GUROBI_CMD","options":{...}}).

Returns:

A minimum dominating set of nodes.

Return type:

set of hashable

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> S = gc.minimum_dominating_set(G)
>>> len(S)
2
graphcalc.graphs.invariants.domination.minimum_double_roman_dominating_function(graph: Graph, *, verbose: bool = False, solve=None) → Dict[str, Dict[Hashable, int] | float][source]

Compute a minimum double Roman dominating function (DRDF) via integer programming.

A double Roman dominating function is a labeling \(f:V(G)\to\{0,1,2,3\}\) such that:

1. If \(f(v)=0\), then either some neighbor of \(v\) has label 3, or at least two neighbors of \(v\) have label 2. 2. If \(f(v)=1\), then some neighbor of \(v\) has label at least 2.

We use binary indicators for each vertex \(v\):

  • \(x_v=1\) iff \(f(v)=1\)

  • \(y_v=1\) iff \(f(v)=2\)

  • \(z_v=1\) iff \(f(v)=3\)

with exclusivity \(x_v+y_v+z_v\le 1\). The objective is

\[\min \sum_{v\in V} (x_v + 2y_v + 3z_v).\]

Formulation

Domination constraint for vertices that may be labeled 0 (linearized):

\[x_v + y_v + z_v \;+\; \tfrac{1}{2}\sum_{u\in N(v)} y_u \;+\; \sum_{u\in N(v)} z_u \;\ge\; 1 \quad \forall v\in V.\]

Domination constraint for vertices labeled 1:

\[\sum_{u\in N(v)} (y_u + z_u) \;\ge\; x_v \quad \forall v\in V.\]

Exclusivity:

\[x_v + y_v + z_v \;\le\; 1 \quad \forall v\in V.\]
param graph:

Undirected input graph.

type graph:

networkx.Graph or graphcalc.SimpleGraph

param verbose:

If True, print solver output (when supported).

type verbose:

bool, default=False

Notes

Accepts standard solver kwargs via graphcalc.solvers.with_solver() (e.g., solver="highs" or solver={"name":"GUROBI_CMD","options":{...}}).

returns:

A dictionary with keys:

  • "x": dict mapping v to 0/1 indicating whether \(f(v)=1\)

  • "y": dict mapping v to 0/1 indicating whether \(f(v)=2\)

  • "z": dict mapping v to 0/1 indicating whether \(f(v)=3\)

  • "objective": float, the minimum value \(\sum_v (x_v + 2y_v + 3z_v)\)

rtype:

dict

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> sol = gc.minimum_double_roman_dominating_function(G)
>>> isinstance(sol["objective"], float)
True
graphcalc.graphs.invariants.domination.minimum_independent_dominating_set(G: Graph, *, verbose: bool = False, solve=None) → Set[Hashable][source]

Find a minimum independent dominating set of \(G\) via integer programming.

An independent dominating set is a set \(S \subseteq V(G)\) such that:

  • (Independent) no two vertices of \(S\) are adjacent, and

  • (Dominating) every vertex of \(G\) is in \(S\) or adjacent to a vertex in \(S\).

Equivalently, \(S\) is both an independent set and a dominating set.

Let \(x_v \in \{0,1\}\) indicate whether \(v\) is chosen. We solve

\[\min \sum_{v \in V} x_v\]

subject to the independence constraints

\[x_u + x_v \le 1 \quad \forall \{u,v\}\in E,\]

and the domination constraints (using the closed neighborhood)

\[\sum_{u \in N[v]} x_u \ge 1 \quad \forall v \in V.\]

Notes

Accepts the standard solver kwargs from graphcalc.solvers.with_solver() (e.g., solver="highs", solver={"name":"GUROBI_CMD","options":{...}}).

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • verbose (bool, default=False) – If True, print solver output (when supported).

Returns:

A minimum independent dominating set.

Return type:

set of hashable

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> S = gc.minimum_independent_dominating_set(G)
>>> len(S)
2
graphcalc.graphs.invariants.domination.minimum_outer_connected_dominating_set(G: Graph) → Set[Hashable][source]

Finds a minimum outer-connected dominating set for the graph \(G\) by trying all subset sizes.

Parameters:

G (networkx.Graph)

Returns:

A minimum outer-connected dominating set of nodes in G.

Return type:

set

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> optimal_set = gc.minimum_outer_connected_dominating_set(G)
graphcalc.graphs.invariants.domination.minimum_rainbow_dominating_function(G: Graph, k: int, *, verbose: bool = False, solve=None) → Tuple[List[Tuple[Hashable, int]], List[Hashable]][source]

Compute a minimum $k$-rainbow dominating function (RDF) via integer programming.

A rainbow dominating function on $G=(V,E)$ with parameter $k$ assigns to each vertex either one of $k$ colors or leaves it uncolored, such that every uncolored vertex is adjacent to at least one vertex of each of the $k$ colors. The objective is to minimize the number of colored vertices.

Variables

  • $f_{v,i} in {0,1}$ — vertex $v$ is colored with color $i in {1,dots,k}$.

  • $x_v in {0,1}$ — vertex $v$ is uncolored.

Objective

\[\min \sum_{v\in V} \sum_{i=1}^k f_{v,i}\]

Constraints

  • Exactly one choice per vertex: .. math:: sum_{i=1}^k f_{v,i} + x_v = 1 quad forall v in V.

  • Rainbow domination (only applies when uncolored): .. math:: sum_{u in N(v)} f_{u,i} ge x_v quad forall vin V,; i=1,dots,k.

param G:

Undirected input graph.

type G:

networkx.Graph or graphcalc.SimpleGraph

param k:

Number of colors (must be >= 1).

type k:

int

param verbose:

If True, print solver output (when supported).

type verbose:

bool, default=False

Notes

Accepts the standard solver kwargs via graphcalc.solvers.with_solver() (e.g., solver="highs", solver={"name":"GUROBI_CMD","options":{...}}).

returns:

(colored_vertices, uncolored_vertices) – colored_vertices is a list of (vertex, color) pairs; uncolored_vertices is a list of vertices with no color.

rtype:

(list[tuple], list)

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> colored, uncolored = gc.minimum_rainbow_dominating_function(G, 2)
>>> len(colored) + len(uncolored) == gc.order(G)
True
graphcalc.graphs.invariants.domination.minimum_restrained_dominating_set(G: Graph, *, verbose: bool = False, solve=None) → Set[Hashable][source]

Compute a minimum restrained dominating set (RDS) via integer programming.

Let \(x_v \in \{0,1\}\) indicate whether \(v\) is in the set \(S\). We minimize \(\sum_v x_v\) subject to:

  • Domination: every vertex is dominated: .. math:: x_v + sum_{u in N(v)} x_u ge 1 quad forall vin V.

  • Restraint: no isolates in the complement \(V\setminus S\): .. math:: sum_{u in N(v)} (1-x_u) ge 1 - x_v quad forall vin V.

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – Undirected input graph.

  • verbose (bool, default=False) – If True, print solver output (when supported).

Notes

Accepts standard solver kwargs via graphcalc.solvers.with_solver() (e.g., solver="highs", solver={"name":"GUROBI_CMD","options":{...}}).

Returns:

A minimum restrained dominating set.

Return type:

set of hashable

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(5)
>>> S = gc.minimum_restrained_dominating_set(G)
>>> len(S) >= 1
True
graphcalc.graphs.invariants.domination.minimum_roman_dominating_function(graph: Graph, *, verbose: bool = False, solve=None) → Dict[str, Dict[Hashable, int] | float][source]

Compute a minimum Roman dominating function (RDF) via integer programming.

A Roman dominating function on \(G=(V,E)\) is a map \(f:V\to\{0,1,2\}\) such that every vertex with label 0 has a neighbor with label 2. The weight of \(f\) is \(\sum_{v\in V} f(v)\).

We minimize the weight using binary indicators:

  • \(x_v=1\) iff \(f(v)=1\)

  • \(y_v=1\) iff \(f(v)=2\)

so that \(f(v)=x_v+2y_v\).

Formulation

\[\min \sum_{v\in V} (x_v + 2y_v)\]
\[x_v + y_v + \sum_{u\in N(v)} y_u \ge 1 \quad \forall v\in V\]
\[x_v + y_v \le 1 \quad \forall v\in V\]
param graph:

Undirected input graph.

type graph:

networkx.Graph or graphcalc.SimpleGraph

param verbose:

If True, print solver output (when supported).

type verbose:

bool, default=False

Notes

Accepts the standard solver kwargs from graphcalc.solvers.with_solver() (e.g., solver="highs", solver={"name":"GUROBI_CMD","options":{...}}).

returns:

A dictionary with keys:

  • "x": dict mapping v to 0/1 indicating whether \(f(v)=1\)

  • "y": dict mapping v to 0/1 indicating whether \(f(v)=2\)

  • "objective": float, the minimum weight \(\sum_v (x_v + 2y_v)\)

rtype:

dict

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> sol = gc.minimum_roman_dominating_function(G)
>>> isinstance(sol["objective"], float)
True
graphcalc.graphs.invariants.domination.minimum_total_domination_set(G: Graph, *, verbose: bool = False, solve=None) → Set[Hashable][source]

Find a minimum total dominating set of \(G\) via integer programming.

Let \(x_v \in \{0,1\}\) indicate whether \(v\) is chosen. We solve

\[\min \sum_{v \in V} x_v \quad \text{s.t.} \quad \sum_{u \in N(v)} x_u \ge 1 \;\; \forall v \in V,\]

where \(N(v)\) is the open neighborhood of \(v\) (no vertex dominates itself).

Notes

  • If \(G\) has an isolated vertex (degree 0), no total dominating set exists. This function raises ValueError in that case.

  • Accepts standard solver kwargs via graphcalc.solvers.with_solver() (e.g., solver="highs", solver={"name":"GUROBI_CMD","options":{...}}).

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • verbose (bool, default=False) – If True, print solver output (when supported).

Returns:

A minimum total dominating set.

Return type:

set of hashable

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> S = gc.minimum_total_domination_set(G)
>>> len(S)
2
graphcalc.graphs.invariants.domination.outer_connected_domination_number(G: Graph) → int[source]

Finds a minimum outer-connected dominating set for the graph \(G\).

A minimum outer-connected dominating set is the smallest subset \(S \subseteq V\) of the graph \(G\) such that:

  1. \(S\) is a dominating set.

  2. The subgraph induced by the complement of \(S\) is connected.

This function tries all subset sizes to find the smallest outer-connected dominating set.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

A minimum outer-connected dominating set of nodes in G.

Return type:

set

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.outer_connected_domination_number(G)
2

Notes

This implementation is exponential in complexity \(O(2^n)\), as it tries all subsets of nodes in the graph. It is not suitable for large graphs.

graphcalc.graphs.invariants.domination.rainbow_domination_number(G: Graph, k: int, **solver_kwargs) → int[source]

Return the rainbow domination number $gamma_{r,k}(G)$.

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – Undirected input graph.

  • k (int) – Number of colors (>= 1).

  • verbose (bool, default=False)

  • solver (str or dict or pulp.LpSolver or type or callable or None, optional)

  • solver_options (dict, optional) – Forwarded to minimum_rainbow_dominating_function().

Returns:

$gamma_{r,k}(G)$ — the minimum number of colored vertices.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> gc.rainbow_domination_number(G, 2)
3
graphcalc.graphs.invariants.domination.restrained_domination_number(G: Graph, **solver_kwargs) → int[source]

Return the restrained domination number \(\gamma_r(G)\).

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – Undirected input graph.

  • verbose (bool, default=False)

  • solver (str or dict or pulp.LpSolver or type or callable or None, optional)

  • solver_options (dict, optional) – Forwarded to minimum_restrained_dominating_set().

Returns:

\(\gamma_r(G)\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> gc.restrained_domination_number(path_graph(5))
3
graphcalc.graphs.invariants.domination.roman_domination_number(graph: Graph, **solver_kwargs) → int[source]

Return the Roman domination number \(\gamma_R(G)\).

Parameters:

  • graph (networkx.Graph or graphcalc.SimpleGraph) – Undirected input graph.

  • verbose (bool, default=False)

  • solver (str or dict or pulp.LpSolver or type or callable or None, optional)

  • solver_options (dict, optional) – Forwarded to minimum_roman_dominating_function().

Returns:

\(\gamma_R(G)\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> gc.roman_domination_number(path_graph(4))
3
graphcalc.graphs.invariants.domination.three_rainbow_domination_number(G: Graph, **solver_kwargs) → int[source]

Return the 3-rainbow domination number $gamma_{r,3}(G)$.

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – Undirected input graph.

  • verbose (bool, default=False)

  • solver (str or dict or pulp.LpSolver or type or callable or None, optional)

  • solver_options (dict, optional) – Forwarded to minimum_rainbow_dominating_function().

Returns:

$gamma_{r,3}(G)$.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> gc.three_rainbow_domination_number(path_graph(4))
4
graphcalc.graphs.invariants.domination.total_domination_number(G: Graph, **solver_kwargs) → int[source]

Return the total domination number of \(G\).

The total domination number is the size of the smallest set \(S\) such that every vertex is adjacent to some vertex in \(S\) (no vertex may dominate itself).

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • verbose (bool, default=False)

  • solver (str or dict or pulp.LpSolver or type or callable or None, optional)

  • solver_options (dict, optional) – Forwarded to minimum_total_domination_set().

Returns:

The total domination number.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> gc.total_domination_number(path_graph(4))
2
graphcalc.graphs.invariants.domination.two_rainbow_domination_number(G: Graph, **solver_kwargs) → int[source]

Return the 2-rainbow domination number $gamma_{r,2}(G)$.

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – Undirected input graph.

  • verbose (bool, default=False)

  • solver (str or dict or pulp.LpSolver or type or callable or None, optional)

  • solver_options (dict, optional) – Forwarded to minimum_rainbow_dominating_function().

Returns:

$gamma_{r,2}(G)$.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> gc.two_rainbow_domination_number(path_graph(4))
3