critical invariants

Critical Invariants

graphcalc.graphs.invariants.critical_invariants.domination_edge_change_number(G)

Count edges whose deletion changes the domination number.

This returns the number of edges \(e\) such that

\[\gamma(G-e) \ne \gamma(G).\]

Parameters:

G (networkx.Graph-like) – A finite graph, intended for simple undirected graphs.

Returns:

The number of edges whose deletion changes \(\gamma(G)\). Returns 0 if \(G\) has no edges.

Return type:

int

Notes

This is a thin wrapper around edge_critical_number() with f = gc.domination_number and kind = 'change'.

Complexity

\(O(|E(G)|)\) evaluations of gc.domination_number on single-edge-deleted graphs.

graphcalc.graphs.invariants.critical_invariants.domination_edge_decrease_number(G)

Count edges whose deletion decreases the domination number.

This returns the number of edges \(e\) such that

\[\gamma(G-e) < \gamma(G).\]

Parameters:

G (networkx.Graph-like) – A finite graph, intended for simple undirected graphs.

Returns:

The number of edges whose deletion decreases \(\gamma(G)\). Returns 0 if \(G\) has no edges.

Return type:

int

Notes

This is a thin wrapper around edge_critical_number() with f = gc.domination_number and kind = 'decrease'.

Complexity

\(O(|E(G)|)\) evaluations of gc.domination_number on single-edge-deleted graphs.

graphcalc.graphs.invariants.critical_invariants.domination_edge_increase_number(G)

Count edges whose deletion increases the domination number.

For each edge \(e \in E(G)\), define the edge-deletion delta

\[\Delta_e \gamma(G) \;:=\; \gamma(G-e) - \gamma(G),\]

where \(G-e\) is the graph obtained by deleting \(e\) (keeping all vertices).

This function returns

\[c_e^+(\gamma)(G) \;=\; \bigl|\{\, e \in E(G) : \gamma(G-e) > \gamma(G) \,\}\bigr|.\]

Intuition: these are edges whose removal makes the graph harder to dominate (typically by reducing adjacency options).

Parameters:

G (networkx.Graph-like) – A finite graph, intended for simple undirected graphs.

Returns:

The number of edges \(e\) with \(\gamma(G-e) > \gamma(G)\). Returns 0 if \(G\) has no edges.

Return type:

int

Notes

This is a thin wrapper around edge_critical_number() with f = gc.domination_number and kind = 'increase'.

Complexity

\(O(|E(G)|)\) evaluations of gc.domination_number on single-edge-deleted graphs.

graphcalc.graphs.invariants.critical_invariants.domination_edge_max_jump(G)

Compute the maximum absolute change in domination number under deletion of a single edge.

This returns:

\[\max_{e\in E(G)} \bigl|\gamma(G-e) - \gamma(G)\bigr|.\]

Parameters:

G (networkx.Graph-like) – A finite graph, intended for simple undirected graphs.

Returns:

The maximum absolute edge-deletion delta for \(\gamma\). Returns 0 if \(G\) has no edges.

Return type:

int

Notes

This computes edge-deletion deltas via edge_deletion_deltas() and returns the maximum absolute value (0 if there are no edges).

Complexity

\(O(|E(G)|)\) evaluations of gc.domination_number on single-edge-deleted graphs.

graphcalc.graphs.invariants.critical_invariants.domination_edge_same_number(G)

Count edges whose deletion leaves the domination number unchanged.

This returns the number of edges \(e\) such that

\[\gamma(G-e) = \gamma(G).\]

Parameters:

G (networkx.Graph-like) – A finite graph, intended for simple undirected graphs.

Returns:

The number of edges whose deletion does not change \(\gamma(G)\). Returns 0 if \(G\) has no edges.

Return type:

int

Notes

This is a thin wrapper around edge_critical_number() with f = gc.domination_number and kind = 'same'.

Complexity

\(O(|E(G)|)\) evaluations of gc.domination_number on single-edge-deleted graphs.

graphcalc.graphs.invariants.critical_invariants.domination_vertex_change_number(G)

Count vertices whose deletion changes the domination number.

This returns the number of vertices \(v\) such that

\[\gamma(G-v) \ne \gamma(G).\]

Equivalently, it counts vertices with nonzero deletion delta \(\Delta_v\gamma(G)=\gamma(G-v)-\gamma(G)\ne 0\).

Parameters:

G (networkx.Graph-like) – A finite graph.

Returns:

The number of vertices whose deletion changes \(\gamma(G)\). Returns 0 if \(G\) has no vertices.

Return type:

int

Notes

This is a thin wrapper around vertex_critical_number() with f = gc.domination_number and kind = 'change'.

Complexity

\(O(|V(G)|)\) evaluations of gc.domination_number on vertex-deleted induced subgraphs.

See also

domination_vertex_increase_number, domination_vertex_decrease_number

graphcalc.graphs.invariants.critical_invariants.domination_vertex_decrease_number(G)

Count vertices whose deletion decreases the domination number.

Using \(\gamma(G)\) for domination number and \(\Delta_v\gamma(G)=\gamma(G-v)-\gamma(G)\), this function returns

\[c_v^-(\gamma)(G) \;=\; \bigl|\{\, v \in V(G) : \gamma(G-v) < \gamma(G) \,\}\bigr| \;=\; \bigl|\{\, v \in V(G) : \Delta_v \gamma(G) < 0 \,\}\bigr|.\]

Intuition: deleting such a vertex makes the remaining graph easier to dominate.

Parameters:

G (networkx.Graph-like) – A finite graph.

Returns:

The number of vertices \(v\) with \(\gamma(G-v) < \gamma(G)\). Returns 0 if \(G\) has no vertices.

Return type:

int

Notes

This is a thin wrapper around vertex_critical_number() with f = gc.domination_number and kind = 'decrease'.

Complexity

\(O(|V(G)|)\) evaluations of gc.domination_number on vertex-deleted induced subgraphs.

See also

domination_vertex_increase_number, domination_vertex_change_number

graphcalc.graphs.invariants.critical_invariants.domination_vertex_increase_number(G)

Count domination-increase-critical vertices of a graph.

Let \(\gamma(G)\) denote the domination number of a graph \(G\). For each vertex \(v \in V(G)\), define the vertex-deletion delta

\[\Delta_v \gamma(G) \;:=\; \gamma(G-v) - \gamma(G),\]

where \(G-v\) is the induced subgraph obtained by deleting \(v\).

This function returns the number of vertices whose deletion increases the domination number:

\[c_v^+(\gamma)(G) \;=\; \bigl|\{\, v \in V(G) : \gamma(G-v) > \gamma(G) \,\}\bigr| \;=\; \bigl|\{\, v \in V(G) : \Delta_v \gamma(G) > 0 \,\}\bigr|.\]

Intuition: these are vertices whose removal makes the remaining graph harder to dominate (more dominators are needed).

Parameters:

G (networkx.Graph-like) – A finite graph.

Returns:

The number of vertices \(v\) with \(\gamma(G-v) > \gamma(G)\). Returns 0 if \(G\) has no vertices.

Return type:

int

Notes

• For minimization parameters like \(\gamma\), this “increase under deletion” notion is the closest analogue of a critical vertex in the sense that deleting it worsens the optimum.

• This is a thin wrapper around vertex_critical_number() with f = gc.domination_number and kind = 'increase'.

Complexity

Dominated by vertex_critical_number() / vertex_deletion_deltas(): performs \(O(|V(G)|)\) evaluations of gc.domination_number on vertex-deleted induced subgraphs.

See also

domination_vertex_decrease_number, domination_vertex_change_number, domination_vertex_max_jump

graphcalc.graphs.invariants.critical_invariants.domination_vertex_max_jump(G)

Compute the maximum absolute change in domination number under deletion of a single vertex.

Let \(\gamma(G)\) denote the domination number. This function returns:

\[\max_{v\in V(G)} \bigl|\gamma(G-v) - \gamma(G)\bigr|.\]

Parameters:

G (networkx.Graph-like) – A finite graph.

Returns:

The maximum absolute vertex-deletion delta for \(\gamma\). Returns 0 if \(G\) has no vertices.

Return type:

int

Notes

This is a one-vertex sensitivity measure for domination number, implemented as a thin wrapper around vertex_deletion_max_jump() with f = gc.domination_number.

Complexity

\(O(|V(G)|)\) evaluations of gc.domination_number on vertex-deleted induced subgraphs.

graphcalc.graphs.invariants.critical_invariants.domination_vertex_same_number(G)

Count vertices whose deletion leaves the domination number unchanged.

This returns the number of vertices \(v\) such that

\[\gamma(G-v) = \gamma(G).\]

Parameters:

G (networkx.Graph-like) – A finite graph.

Returns:

The number of vertices whose deletion does not change \(\gamma(G)\). Returns 0 if \(G\) has no vertices.

Return type:

int

Notes

This is a thin wrapper around vertex_critical_number() with f = gc.domination_number and kind = 'same'.

Complexity

\(O(|V(G)|)\) evaluations of gc.domination_number on vertex-deleted induced subgraphs.

graphcalc.graphs.invariants.critical_invariants.edge_critical_number(G, f, *, kind='change')

Count edges by how a graph parameter \(f\) changes under single-edge deletion.

For each edge \(e \in E(G)\), define the edge-deletion delta

\[\Delta_e f(G) \;:=\; f(G - e) - f(G),\]

where \(G-e\) is the graph obtained from \(G\) by deleting the edge \(e\) (keeping all vertices). This function counts how many edges fall into a given sign class of \(\Delta_e f(G)\):

• kind='change': edges with \(\Delta_e f(G) \neq 0\)

• kind='increase': edges with \(\Delta_e f(G) > 0\)

• kind='decrease': edges with \(\Delta_e f(G) < 0\)

• kind='same': edges with \(\Delta_e f(G) = 0\)

Parameters:

• G (networkx.Graph-like) – A finite graph, intended for simple undirected graphs (so that edges are naturally unordered and uniquely determined by their endpoints). The deltas are computed by edge_deletion_deltas(), which is not designed for multigraph edge keys.

• f (callable) – A function f(H) -> number defined on graphs H.

• kind ({'change', 'increase', 'decrease', 'same'}, optional) – Which deletion behavior to count.

Returns:

The number of edges \(e\) satisfying the requested condition on \(\Delta_e f(G)\). If \(|E(G)|=0\), returns 0.

Return type:

int

Raises:

• ValueError – If kind is not one of {'change','increase','decrease','same'}.

• Exception – Propagates any exception raised by f when evaluated on G or on any edge-deleted graph (via edge_deletion_deltas()).

Notes

• Terminology varies: some authors reserve “edge-critical” for a specific direction of change, e.g.:

  • for maximization parameters (such as \(\alpha\) or \(\omega\)), edges with kind='decrease';

  • for minimization parameters (such as \(\chi\)), edges with kind='increase'.

• This function is agnostic and provides all four sign-based categories via kind.

• This is a counting wrapper; if you want the edges themselves, define an analogous edge_critical_set using the same delta predicate.

Complexity

Dominated by edge_deletion_deltas(): \(O(|E(G)|)\) evaluations of f on graphs with one edge deleted (plus one evaluation on G), and then an \(O(|E(G)|)\) scan to count.

graphcalc.graphs.invariants.critical_invariants.edge_deletion_deltas(G, f)

Compute single-edge deletion deltas for a graph parameter \(f\).

For each edge \(e \in E(G)\), form the graph obtained by deleting that edge while keeping all vertices, and compute the delta:

\[\Delta_e f(G) \;:=\; f(G - e) - f(G),\]

where \(G-e\) denotes the graph with edge \(e\) removed (vertex set unchanged).

The function returns the mapping \(e \mapsto \Delta_e f(G)\) for all edges of \(G\).

Parameters:

• G (networkx.Graph-like) –

  A finite graph. This routine is primarily intended for simple undirected graphs.

  • For a DiGraph, “edge deletion” refers to deleting a directed arc, and edges are ordered. This function still iterates G.edges() but then collapses each edge to an unordered key (a frozenset), which is generally not appropriate for directed graphs.

  • For a MultiGraph / MultiDiGraph, parallel edges require edge keys to distinguish copies; this function does not accept edge keys and is therefore not suitable without adaptation.

• f (callable) – A function f(H) -> number defined on graphs H. The value is evaluated on G and on each edge-deleted graph G-e.

Returns:

A dictionary mapping each edge to the numeric value f(G - e) - f(G).

Edges are keyed as frozenset({u, v}) so they are treated as unordered, and node labels need not be comparable. For a simple undirected graph, this keying gives a one-to-one correspondence between edges and dictionary entries.

If \(|E(G)| = 0\), returns an empty dictionary {}.

Return type:

dict

Raises:

Exception – Propagates any exception raised by f when evaluated on G or on any edge-deleted graph.

Notes

• The implementation copies G once per edge and deletes that edge. This protects the original graph from mutation regardless of whether f mutates its input.

• These deltas are useful for edge-sensitivity / edge-criticality analyses: they quantify how much the parameter changes when a single edge is removed.

Complexity

Let \(m=|E(G)|\). This routine performs \(m+1\) evaluations of f (once on G and once for each of the \(m\) single-edge deletions). The total runtime is dominated by the cost of evaluating f on graphs with one edge removed, plus the overhead of copying the graph:

\[O\!\left(m \cdot T_f(n, m-1)\right),\]

where \(T_f\) is the time to evaluate f on a graph of the given size.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(5)
>>> d = gc.edge_deletion_deltas(G, gc.chromatic_number)
>>> all(v <= 0 for v in d.values())  # removing an edge cannot increase chi for simple graphs
True

graphcalc.graphs.invariants.critical_invariants.vertex_critical_number(G, f, *, kind='change')

Count vertices by how a graph parameter \(f\) changes under single-vertex deletion.

This is the cardinality of vertex_critical_set():

\[\bigl|\{\, v \in V(G) : \Delta_v f(G)\ \text{satisfies the requested condition}\,\}\bigr|,\]

where

\[\Delta_v f(G) \;=\; f(G - v) - f(G)\]

and \(G-v\) denotes the induced subgraph obtained by deleting \(v\).

The kind argument specifies which condition is used:

• kind='change': \(\Delta_v f(G) \neq 0\)

• kind='increase': \(\Delta_v f(G) > 0\)

• kind='decrease': \(\Delta_v f(G) < 0\)

• kind='same': \(\Delta_v f(G) = 0\)

Parameters:

• G (networkx.Graph-like) – A finite graph.

• f (callable) – A function f(H) -> number defined on graphs H.

• kind ({'change', 'increase', 'decrease', 'same'}, optional) – Which deletion behavior to count.

Returns:

The number of vertices in \(G\) whose deletion has the specified effect on \(f\).

If \(|V(G)|=0\), this returns 0.

Return type:

int

Raises:

• ValueError – If kind is not one of {'change','increase','decrease','same'}.

• Exception – Propagates any exception raised by f when evaluated on G or on a vertex-deleted induced subgraph (via vertex_critical_set() / vertex_deletion_deltas()).

Notes

This is a thin wrapper around vertex_critical_set() that returns only the count.

Complexity

Same as vertex_critical_set(): dominated by \(O(|V(G)|)\) evaluations of f on vertex-deleted induced subgraphs (plus one evaluation on G).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(6)
>>> gc.vertex_critical_number(G, gc.independence_number, kind="change")
0

graphcalc.graphs.invariants.critical_invariants.vertex_critical_set(G, f, *, kind='change')

Select vertices by how a graph parameter \(f\) changes under single-vertex deletion.

For each vertex \(v \in V(G)\), define the vertex-deletion delta

\[\Delta_v f(G) \;:=\; f(G - v) - f(G),\]

where \(G - v\) is the induced subgraph obtained by deleting \(v\).

This function returns the subset of vertices classified by the sign (or nonzero-ness) of \(\Delta_v f(G)\):

• kind='change': vertices with \(\Delta_v f(G) \neq 0\) (deletion changes the value)

• kind='increase': vertices with \(\Delta_v f(G) > 0\) (value increases after deletion)

• kind='decrease': vertices with \(\Delta_v f(G) < 0\) (value decreases after deletion)

• kind='same': vertices with \(\Delta_v f(G) = 0\) (value unchanged after deletion)

Parameters:

• G (networkx.Graph-like) – A finite graph.

• f (callable) – A function f(H) -> number defined on graphs H. The value is evaluated on G and on each induced subgraph G - v.

• kind ({'change', 'increase', 'decrease', 'same'}, optional) – Which deletion behavior to select.

Returns:

A set of vertices v satisfying the requested deletion behavior with respect to \(f\).

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

Return type:

set

Raises:

• ValueError – If kind is not one of {'change','increase','decrease','same'}.

• Exception – Propagates any exception raised by f when evaluated on G or on any vertex-deleted induced subgraph.

Notes

• This is a generic vertex-sensitivity / “criticality” selector. Terminology varies by context:

  • For maximization parameters (e.g. \(\alpha\), \(\omega\)), authors sometimes call vertices with kind='decrease' critical, since deleting them reduces the optimum.

  • For minimization parameters (e.g. \(\chi\), \(\gamma\)), authors sometimes call vertices with kind='increase' critical, since deleting them increases the minimum.

• This function does not assume whether \(f\) is a max or min parameter; it simply filters by the sign of \(\Delta_v f(G)\).

• The deltas are computed by vertex_deletion_deltas(), which forms induced subgraphs and evaluates f on them.

Complexity

Dominated by computing the deltas: \(O(|V(G)|)\) evaluations of f on graphs with one vertex deleted (plus one evaluation on G itself). The additional filtering is \(O(|V(G)|)\).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(5)
>>> # Vertices whose deletion changes the independence number:
>>> gc.vertex_critical_set(G, gc.independence_number, kind="change")
{...}

graphcalc.graphs.invariants.critical_invariants.vertex_deletion_deltas(G, f)

Compute single-vertex deletion deltas for a graph parameter \(f\).

For each vertex \(v \in V(G)\), form the induced vertex-deleted subgraph

\[G - v \;:=\; G[V(G)\setminus\{v\}],\]

and compute the deletion delta

\[\Delta_v f(G) \;:=\; f(G - v) - f(G).\]

The function returns the mapping \(v \mapsto \Delta_v f(G)\) for all vertices of \(G\).

Parameters:

• G (networkx.Graph-like) – A finite graph.

• f (callable) –

  A function f(H) -> number defined on graphs H.

  Examples include invariants/parameters such as order, size, independence_number, clique_number, domination_number, and chromatic_number.

  The function is evaluated first on G and then on each induced subgraph G - v.

Returns:

A dictionary mapping each vertex v of G to the numeric value f(G - v) - f(G).

If \(|V(G)|=0\), returns the empty dictionary {}.

Return type:

dict

Notes

• These deltas are useful for sensitivity and criticality analyses.

• The induced subgraph G - v is passed to f as a .copy() to protect against accidental mutation inside f. If f is guaranteed to be read-only, you may omit .copy() for speed.

Raises:

Exception – Propagates any exception raised by f when applied to G or to any vertex-deleted induced subgraph.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(4)
>>> d = gc.vertex_deletion_deltas(G, gc.order)
>>> d[0], d[1], d[2], d[3]
(-1, -1, -1, -1)

graphcalc.graphs.invariants.critical_invariants.vertex_deletion_max_jump(G, f)

Compute the maximum one-vertex deletion jump of a graph parameter \(f\).

For each vertex \(v \in V(G)\), consider the vertex-deletion delta

\[\Delta_v f(G) \;=\; f(G - v) - f(G),\]

where \(G - v\) is the induced subgraph obtained by deleting \(v\). This function returns the maximum absolute change over all single-vertex deletions:

\[J_{\max}(G;f) \;=\; \max_{v \in V(G)} \bigl|f(G - v) - f(G)\bigr| \;=\; \max_{v \in V(G)} |\Delta_v f(G)|.\]

Parameters:

• G (networkx.Graph-like) – A finite graph.

• f (callable) – A function f(H) -> number defined on graphs H.

Returns:

The maximum absolute delta \(\max_v |\Delta_v f(G)|\). If \(|V(G)| = 0\), returns 0.

Return type:

number

Raises:

Exception – Propagates any exception raised by f when evaluated on G or on any vertex-deleted induced subgraph (via vertex_deletion_deltas()).

Notes

• This is a simple one-vertex sensitivity measure for \(f\): it quantifies the largest single-vertex deletion impact on the parameter value.

• If \(G\) is empty, there are no deletions to consider, so the maximum jump is defined here to be 0.

• The deltas are computed by vertex_deletion_deltas(), which evaluates f on G and on each induced subgraph G-v.

Complexity

Dominated by computing the deltas: \(O(|V(G)|)\) evaluations of f on graphs with one vertex deleted (plus one evaluation on G), and then an \(O(|V(G)|)\) scan to take the maximum.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.path_graph(6)
>>> gc.vertex_deletion_max_jump(G, gc.zero_forcing_number)
1