zero forcing

Zero Forcing

graphcalc.graphs.invariants.zero_forcing.burning_number(G: Graph, *, return_schedule: bool = False, solve=None, **solver_kwargs) → int | Tuple[int, List[Hashable]]

Compute the burning number \(b(G)\) using a mixed-integer program (MIP).

In the graph burning process, one vertex is ignited at each round, and fire spreads one edge per round from every burning vertex. The burning number \(b(G)\) is the minimum number of rounds needed to burn all vertices.

MIP model for a fixed horizon \(T\)

Let \(x_{v,t}\in\{0,1\}\) indicate that vertex \(v\) is chosen as a new ignition source at round \(t\) (for \(t=1,\dots,T\)).

Ignition constraints (one new source per round):

\[\sum_{v\in V} x_{v,t} = 1 \quad \forall t\in\{1,\dots,T\}.\]

Coverage constraints (every vertex burned by time \(T\)): a vertex \(u\) is burned by round \(T\) if there exists an ignition \((v,t)\) with \(d(u,v)\le T-t\), where \(d\) is graph distance. This is enforced by

\[\begin{split}\sum_{t=1}^{T}\;\sum_{\substack{v\in V:\\ d(u,v)\le T-t}} x_{v,t} \;\ge\; 1 \quad \forall u\in V.\end{split}\]

Search strategy

We solve a sequence of feasibility MIPs for \(T = \mathrm{LB}, \mathrm{LB}+1, \dots\) and return the smallest feasible \(T\).

• Lower bound: \(\max(1, \#\text{components}(G))\).

• Upper bound: if \(G\) is connected, \(\mathrm{UB}=\min(n, \mathrm{radius}(G)+1)\); otherwise we use \(\mathrm{UB}=n\), which is always valid.

param G:

Undirected graph (not necessarily connected).

type G:

networkx.Graph or graphcalc.SimpleGraph

param return_schedule:

If True, also return a list [v1, ..., vT] giving the ignition vertices in order.

type return_schedule:

bool, default=False

param verbose:

type verbose:

bool, default=False

param solver:

type solver:

str or dict or pulp.LpSolver or type or callable or None, optional

param solver_options:

Standard solver kwargs accepted by graphcalc.solvers.with_solver().

type solver_options:

dict, optional

returns:

If return_schedule=False, returns the burning number \(b(G)\). If return_schedule=True, returns (b(G), schedule) where schedule is a minimum-length ignition sequence.

rtype:

int or (int, list of hashable)

Notes

This function requires a MILP-capable solver supported by your with_solver() configuration.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(9)
>>> b, sched = gc.burning_number(G, return_schedule=True)
>>> len(sched) == b
True

graphcalc.graphs.invariants.zero_forcing.compute_well_splitting_number(G: Graph | SimpleGraph)

Compute the well-splitting number \(S_w(G)\) of the graph \(G\).

It searches over all subsets \(S \subseteq V(G)\) in increasing size and returns the minimum size r and all candidate sets of that size that are well-splitting.

Parameters:

G (NetworkX Graph.)

Returns:

A tuple (r, valid_sets) where r is the minimum size of a well-splitting set and valid_sets is a list of candidate sets (each given as a tuple of vertices).

Return type:

tuple

graphcalc.graphs.invariants.zero_forcing.connected_k_forcing_number(G: Graph | SimpleGraph, k: int) → int

Calculates the connected kforcing number of the graph G.

The connected zero forcing number is the size of the smallest connected zero forcing set.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph.

• k (int) – A positive integer representing the k-forcing parameter.

Returns:

The connected k-forcing number of G, or None if no such set exists.

Return type:

int

Examples

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

>>> G = path_graph(4)
>>> print(gc.connected_k_forcing_number(G, 1))
1

graphcalc.graphs.invariants.zero_forcing.connected_zero_forcing_number(G: Graph | SimpleGraph) → int

Calculates the connected zero forcing number of the graph G.

The connected zero forcing number is the size of the smallest connected zero forcing set.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph.

Returns:

The connected zero forcing number of G, or None if no such set exists.

Return type:

int

Examples

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

>>> G = path_graph(4)
>>> print(gc.connected_zero_forcing_number(G))
1

graphcalc.graphs.invariants.zero_forcing.is_connected_k_forcing_set(G: Graph | SimpleGraph, nodes: Set[Hashable] | List[Hashable], k: int) → bool

Determines whether the given nodes form a connected k-forcing set in the graph G.

A connected k-forcing set is a k-forcing set that induces a connected subgraph.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph.

• nodes (list or set) – A set of nodes under consideration.

• k (int) – A positive integer representing the k-forcing parameter.

Returns:

True if the nodes form a connected k-forcing set, False otherwise.

Return type:

bool

Examples

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

>>> G = path_graph(4)
>>> nodes = {0, 1}
>>> print(gc.is_connected_k_forcing_set(G, nodes, 1))
True

graphcalc.graphs.invariants.zero_forcing.is_connected_zero_forcing_set(G: Graph | SimpleGraph, S: Set[Hashable] | List[Hashable]) → bool

Determines whether the given nodes form a connected zero forcing set in the graph G.

A connected zero forcing set is a zero forcing set that induces a connected subgraph.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph.

• S (list or set) – A set of nodes under consideration.

Returns:

True if the nodes form a connected k-forcing set, False otherwise.

Return type:

bool

Examples

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

>>> G = path_graph(4)
>>> nodes = {0, 1}
>>> print(gc.is_connected_zero_forcing_set(G, nodes))
True

graphcalc.graphs.invariants.zero_forcing.is_k_forcing_active_set(G: Graph | SimpleGraph, nodes: Set[Hashable] | List[Hashable], k: int) → bool

Checks if at least one node in the given set can perform k-forcing.

Parameters:

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

• nodes (list or set) – The set of nodes under consideration.

• k (int) – The parameter for k-forcing.

Returns:

True if at least one node in nodes can k-force. False otherwise.

Return type:

bool

Examples

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

>>> G = path_graph(4)
>>> nodes = {0, 1}
>>> print(gc.is_k_forcing_active_set(G, nodes, 1))
True

graphcalc.graphs.invariants.zero_forcing.is_k_forcing_set(G: Graph | SimpleGraph, nodes: Set[Hashable] | List[Hashable], k: int) → bool

Determines whether the given set of nodes is a k-forcing set in the graph.

A set of nodes is a k-forcing set if, starting from the set, all nodes in the graph can eventually be included by repeatedly applying the k-forcing rule.

Parameters:

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

• nodes (list or set) – The set of nodes under consideration.

• k (int) – The parameter for k-forcing.

Returns:

True if the nodes form a k-forcing set. False otherwise.

Return type:

bool

Examples

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

>>> G = path_graph(4)
>>> nodes = {0, 2}
>>> print(gc.is_k_forcing_set(G, nodes, 1))
True

graphcalc.graphs.invariants.zero_forcing.is_k_forcing_vertex(G: Graph | SimpleGraph, v: Hashable, nodes: Set[Hashable] | List[Hashable], k: int) → bool

Determines whether a node v can perform k-forcing with respect to a set of nodes.

A node v is said to k-force if it is in the set nodes and has between 1 and k neighbors not in nodes.

Parameters:

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

• v (node) – The node to check for k-forcing.

• nodes (list or set) – The set of nodes under consideration.

• k (int) – The parameter for k-forcing, which must be a positive integer.

Returns:

True if v can k-force relative to nodes. False otherwise.

Return type:

bool

Raises:

• TypeError – If k is not an integer.

• ValueError – If k is not a positive integer.

Examples

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

>>> G = path_graph(4)
>>> nodes = {0, 1}
>>> print(gc.is_k_forcing_vertex(G, 1, nodes, 1))
True

graphcalc.graphs.invariants.zero_forcing.is_k_power_dominating_set(G: Graph | SimpleGraph, nodes: Set[Hashable] | List[Hashable], k: int) → bool

Checks if the given nodes comprise a k-power dominating set in the graph G.

A k-power dominating set is a subset of nodes such that all nodes in the graph can be dominated through the k-forcing process. The k-forcing process begins with the closed neighborhood of the given nodes, and iteratively propagates domination by ensuring each dominated node dominates at least k additional nodes in its neighborhood.

Parameters:

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

• nodes (list or set) – An iterable container of nodes in G to test as a k-power dominating set.

• k (int) – A positive integer representing the power domination threshold.

Returns:

True if the nodes form a k-power dominating set, otherwise False.

Return type:

bool

Notes

• The closed neighborhood of a node v in a graph G includes v itself and all its neighbors.

• A k-power dominating set is a generalization of the concept of domination in graphs.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc

>>> G = nx.path_graph(5)
>>> nodes = {0}
>>> print(gc.is_k_power_dominating_set(G, nodes, 2))
True

graphcalc.graphs.invariants.zero_forcing.is_power_dominating_set(G: Graph | SimpleGraph, nodes: Set[Hashable] | List[Hashable]) → bool

Checks if the given nodes form a power dominating set in the graph G.

A power dominating set is a 1-power dominating set, meaning the domination process follows the 1-forcing rule starting from the closed neighborhood of the nodes.

Parameters:

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

• nodes (list or set) – An iterable container of nodes in G.

Returns:

True if the nodes form a power dominating set, otherwise False.

Return type:

bool

Examples

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

>>> G = path_graph(4)
>>> nodes = {0}
>>> print(gc.is_power_dominating_set(G, nodes))
True

graphcalc.graphs.invariants.zero_forcing.is_psd_forcing_vertex(G: Graph | SimpleGraph, v: Hashable, component: Set[Hashable]) → bool

Determines whether a node v can perform positive semidefinite (PSD) forcing in a specific component.

A node v in the black set can force a single white vertex in a connected component of G - black_set if it has exactly one white neighbor in that component.

Parameters:

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

• v (node) – A single node in G.

• component (set) – A set of nodes representing a connected component of G - black_set.

Returns:

(True, w) if v can force the white vertex w in the component, (False, None) otherwise.

Return type:

tuple

Examples

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

>>> G = path_graph(4)
>>> black_set = {0, 1}
>>> component = {2, 3}
>>> print(gc.is_psd_forcing_vertex(G, 1, component))
(True, 2)

graphcalc.graphs.invariants.zero_forcing.is_psd_zero_forcing_set(G: Graph | SimpleGraph, black_set: Set[Hashable]) → bool

Determines whether the given set of black vertices is a PSD zero forcing set.

A PSD zero forcing set is a set of vertices that, through iterative application of the PSD color change rule, results in all vertices of the graph being black.

Parameters:

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

• black_set (set) – A set of initial black vertices.

Returns:

True if the given set is a PSD zero forcing set, otherwise False.

Return type:

bool

Examples

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

>>> G = path_graph(4)
>>> black_set = {0, 3}
>>> print(gc.is_psd_zero_forcing_set(G, black_set))
True

graphcalc.graphs.invariants.zero_forcing.is_total_zero_forcing_set(G: Graph | SimpleGraph, S: Set[Hashable] | List[Hashable]) → bool

Checks if the given nodes form a total zero forcing set.

A total zero forcing set is a zero forcing set that does not induce any isolated vertices.

Parameters:

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

• S (list or set) – The set of nodes under consideration.

Returns:

True if the nodes form a total zero forcing set. False otherwise.

Return type:

bool

Examples

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

>>> G = path_graph(4)
>>> nodes = {0, 1}
>>> print(gc.is_total_zero_forcing_set(G, nodes))
True

graphcalc.graphs.invariants.zero_forcing.is_well_splitting_set(G: Graph | SimpleGraph, S: Set[Hashable] | List[Hashable]) → bool

Check if G is a well-splitting set of G

Parameters:

• G (nx.Graph)

• S (set)

Returns:

True if S is well-splitting, False otherwise.

Return type:

bool

graphcalc.graphs.invariants.zero_forcing.is_zero_forcing_set(G: Graph | SimpleGraph, S: Set[Hashable] | List[Hashable]) → bool

Checks whether the given set of nodes forms a zero forcing set in the graph.

A zero forcing set is a special case of a k-forcing set where k = 1.

Parameters:

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

• S (list or set) – The set of nodes under consideration.

Returns:

True if the nodes form a zero forcing set. False otherwise.

Return type:

bool

Examples

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

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

graphcalc.graphs.invariants.zero_forcing.is_zero_forcing_vertex(G: Graph | SimpleGraph, v: Hashable, S: Set[Hashable] | List[Hashable]) → bool

Determines whether a node v can force relative to a set of nodes.

This is a special case of k-forcing where k = 1.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph.

• v (node) – The node to check.

• S (list or set) – The set of nodes under consideration.

Returns:

True if v can force. False otherwise.

Return type:

bool

Examples

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

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

graphcalc.graphs.invariants.zero_forcing.k_forcing_number(G: Graph | SimpleGraph, k: int) → int

Calculates the k-forcing number of the graph.

The k-forcing number is the size of the smallest k-forcing set.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph.

• k (int) – The parameter for k-forcing.

Returns:

The k-forcing number.

Return type:

int

Examples

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

>>> G = path_graph(4)
>>> print(gc.k_forcing_number(G, 1))
1

graphcalc.graphs.invariants.zero_forcing.k_power_domination_number(G: Graph | SimpleGraph, k: int) → int

Finds the smallest k-power dominating set in the graph G.

This function uses a brute-force approach to identify the minimum subset of vertices that form a k-power dominating set.

Parameters:

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

• k (int) – A positive integer representing the power domination threshold.

Returns:

A set of nodes representing the smallest k-power dominating set.

Return type:

set

Examples

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

>>> G = path_graph(4)
>>> result = gc.minimum_k_power_dominating_set(G, 2)
>>> print(result)
{0}

graphcalc.graphs.invariants.zero_forcing.minimum_connected_k_forcing_set(G: Graph | SimpleGraph, k: int) → Set[Hashable]

Finds the smallest connected k-forcing set in the graph G using brute force.

Parameters:

• G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph.

• k (int) – A positive integer representing the k-forcing parameter.

Returns:

A smallest connected k-forcing set in G, or None if the graph is disconnected.

Return type:

set

Examples

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

>>> G = path_graph(4)
>>> print(gc.minimum_connected_k_forcing_set(G, 1))
{0}

graphcalc.graphs.invariants.zero_forcing.minimum_connected_zero_forcing_set(G: Graph | SimpleGraph) → Set[Hashable]

Finds the smallest connected zero forcing set in the graph G using brute force.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph.

Returns:

A smallest connected zero forcing set in G, or None if the graph is disconnected.

Return type:

set

Examples

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

>>> G = path_graph(4)
>>> print(gc.minimum_connected_zero_forcing_set(G))
{0}

graphcalc.graphs.invariants.zero_forcing.minimum_k_forcing_set(G: Graph | SimpleGraph, k: int) → Set[Hashable]

Finds a smallest k-forcing set in the graph using brute force.

Parameters:

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

• k (int) – The parameter for k-forcing.

Returns:

A smallest k-forcing set.

Return type:

set

Examples

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

>>> G = path_graph(4)
>>> print(gc.minimum_k_forcing_set(G, 1))
{0}

graphcalc.graphs.invariants.zero_forcing.minimum_k_power_dominating_set(G: Graph | SimpleGraph, k: int) → Set[Hashable]

Checks if the given nodes comprise a k-power dominating set in the graph G.

A k-power dominating set is a subset of vertices such that all vertices of the graph can be dominated through the k-forcing process starting from the closed neighborhood of the given nodes.

Parameters:

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

• nodes (list or set) – An iterable container of nodes in G.

• k (int) – A positive integer representing the power domination threshold.

Returns:

True if the given nodes form a k-power dominating set, otherwise False.

Return type:

bool

Examples

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

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

graphcalc.graphs.invariants.zero_forcing.minimum_power_dominating_set(G: Graph | SimpleGraph) → Set[Hashable]

Finds the smallest power dominating set in the graph \(G\).

This function uses a brute-force approach to identify the minimum subset of vertices that form a power dominating set.

Parameters:

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

Returns:

A set of nodes representing the smallest power dominating set.

Return type:

set

Examples

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

>>> G = path_graph(4)
>>> result = gc.minimum_power_dominating_set(G)
>>> print(result)
{0}

graphcalc.graphs.invariants.zero_forcing.minimum_psd_zero_forcing_set(G: Graph | SimpleGraph) → Set[Hashable]

Finds a smallest PSD zero forcing set in the graph G.

The PSD zero forcing set is computed using brute force by iterating through all possible subsets of vertices until a valid set is found.

Parameters:

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

Returns:

A list of nodes representing the smallest PSD zero forcing set in G.

Return type:

list

Examples

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

>>> G = path_graph(4)
>>> result = gc.minimum_psd_zero_forcing_set(G)
>>> print(result)
{0}

graphcalc.graphs.invariants.zero_forcing.minimum_total_zero_forcing_set(G: Graph | SimpleGraph) → Set[Hashable]

Finds a smallest total zero forcing set in the graph G.

A total zero forcing set is a zero forcing set that does not induce any isolated vertices.

Parameters:

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

Returns:

A smallest total zero forcing set in G, or None if none exists.

Return type:

set

Examples

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

>>> G = path_graph(4)
>>> result = gc.minimum_total_zero_forcing_set(G)
>>> print(result)
{0, 1}

graphcalc.graphs.invariants.zero_forcing.minimum_zero_forcing_set(G: Graph | SimpleGraph) → Set[Hashable]

Finds a smallest zero forcing set in the graph using brute force.

Parameters:

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

Returns:

A smallest zero forcing set.

Return type:

set

Examples

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

>>> G = path_graph(4)
>>> gc.minimum_zero_forcing_set(G)
{0}

graphcalc.graphs.invariants.zero_forcing.positive_semidefinite_zero_forcing_number(G: Graph | SimpleGraph) → int

Calculates the Positive Semidefinite (PSD) zero forcing number of the graph G.

The PSD zero forcing number is the size of the smallest PSD zero forcing set in the graph.

Parameters:

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

Returns:

The PSD zero forcing number of G.

Return type:

int

Examples

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

>>> G = path_graph(4)
>>> print(gc.positive_semidefinite_zero_forcing_number(G))
1

graphcalc.graphs.invariants.zero_forcing.power_domination_number(G: Graph | SimpleGraph) → int

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

The power domination number is the size of the smallest power dominating set.

Parameters:

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

Returns:

The power domination number of G.

Return type:

int

Examples

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

>>> G = path_graph(4)
>>> print(gc.power_domination_number(G))
1

graphcalc.graphs.invariants.zero_forcing.psd_color_change(G: Graph | SimpleGraph, black_set: Set[Hashable]) → Set[Hashable]

Applies the Positive Semidefinite (PSD) color change rule to a graph G.

The PSD color change rule allows a black vertex v to force a white vertex w in a connected component of G - black_set if v has exactly one white neighbor in that component. This process is applied iteratively until no more vertices can be forced.

Parameters:

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

• black_set (set) – A set of initial black vertices.

Returns:

The derived set of black vertices after applying the PSD color change rule.

Return type:

set

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc

>>> G = nx.path_graph(5)
>>> black_set = {0}
>>> result = gc.psd_color_change(G, black_set)
>>> print(result)
{0, 1, 2, 3, 4}

graphcalc.graphs.invariants.zero_forcing.total_zero_forcing_number(G: Graph | SimpleGraph) → int

Calculates the total zero forcing number of the graph G.

The total zero forcing number is the size of the smallest total zero forcing set.

Parameters:

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

Returns:

The total zero forcing number of G, or None if no such set exists.

Return type:

int

Examples

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

>>> G = path_graph(4)
>>> print(gc.total_zero_forcing_number(G))
2

graphcalc.graphs.invariants.zero_forcing.two_forcing_number(G: Graph | SimpleGraph) → int

Calculates the 2-forcing number of the graph.

Parameters:

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

Returns:

The 2-forcing number of the graph.

Return type:

int

Examples

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

>>> G = path_graph(4)
>>> print(gc.two_forcing_number(G))
1

graphcalc.graphs.invariants.zero_forcing.well_splitting_number(G: Graph | SimpleGraph) → int

Compute the well-splitting number \(S_w(G)\) of the graph \(G\). The well-splitting number of a graph is the minimum size of a well-splitting set, defined as a set \(S\) of vertices such that every connected component of \(G-S\) has at most \(\lceil\frac{|V(G)| - |S|}{2}\rceil\) vertices. A well-splitting set is a set of vertices whose removal results in a graph where every connected component has a size that is at most half of the remaining vertices.

Parameters:

G (NetworkX Graph.) – The input graph for which the well-splitting number is to be computed.

Returns:

The well-splitting number \(S_w(G)\), which is the minimum size of a well-splitting set. If no such set exists, it returns the size of the entire vertex set.

Return type:

int

Examples

>>> import networkx as nx
>>> from graphcalc.graphs.invariants.zero_forcing import well_splitting_number
>>> G = nx.petersen_graph()
>>> print(well_splitting_number(G))
4
>>> G = nx.complete_graph(5)
>>> print(well_splitting_number(G))
4

graphcalc.graphs.invariants.zero_forcing.zero_forcing_number(G: Graph | SimpleGraph) → int

Calculates the zero forcing number of the graph.

The zero forcing number is the size of the smallest zero forcing set.

Parameters:

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

Returns:

The zero forcing number of the graph.

Return type:

int

Examples

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

>>> G = path_graph(4)
>>> print(gc.zero_forcing_number(G))
1