core invariants

Core Invariants

graphcalc.graphs.invariants.core_invariants.alpha_core_number(G)

Compute the α-core number of a graph: the size of the intersection of all maximum independent sets.

If \(\operatorname{core}_\alpha(G)\) denotes the α-core (the set of vertices contained in every maximum independent set), this function returns its cardinality:

\[|\operatorname{core}_\alpha(G)| \;=\; \left|\bigcap \{\, I \subseteq V(G) : I \text{ is an independent set and } |I|=\alpha(G) \,\}\right|.\]

Parameters:

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

Returns:

The α-core number of \(G\). Returns 0 if \(G\) has no vertices.

Return type:

int

Notes

This is a thin wrapper around alpha_core_set().

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.star_graph(4)
>>> gc.alpha_core_number(G)
4

graphcalc.graphs.invariants.core_invariants.alpha_core_set(G)

Compute the α-core of a graph: the intersection of all maximum independent sets.

Let \(\alpha(G)\) denote the independence number of \(G\), i.e., the maximum size of an independent set. The α-core (also called the core with respect to maximum independent sets) is the set of vertices that belong to every maximum independent set:

\[\operatorname{core}_\alpha(G) \;=\; \bigcap \{\, I \subseteq V(G) : I \text{ is an independent set and } |I|=\alpha(G) \,\}.\]

This implementation uses the standard deletion characterization for independence number:

\[v \in \operatorname{core}_\alpha(G) \iff \alpha(G - v) < \alpha(G),\]

where \(G-v\) is the induced subgraph obtained by deleting \(v\). Equivalently, if \(\alpha(G-v)=\alpha(G)\), then there exists a maximum independent set avoiding \(v\), so \(v\) is not in the intersection of all maximum independent sets.

Parameters:

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

Returns:

The α-core of \(G\), i.e., the set of vertices contained in every maximum independent set. Returns the empty set if \(G\) has no vertices.

Return type:

set

Notes

• The deletion test used here is exact for \(\alpha(G)\) because any maximum independent set of \(G-v\) is also an independent set of \(G\) that avoids \(v\).

• This method requires only \(|V(G)|\) evaluations of \(\alpha(\cdot)\) on vertex-deleted induced subgraphs, and is typically much faster than enumerating all maximum independent sets.

Complexity

Performs \(|V(G)|\) calls to gc.independence_number on graphs with one vertex deleted. Total runtime therefore depends on the complexity of computing \(\alpha(G)\) in your backend.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # In a star, every maximum independent set consists of all leaves, so the α-core is the set of leaves.
>>> G = nx.star_graph(4)  # 5 vertices: center + 4 leaves
>>> gc.alpha_core_set(G) == set(range(1, 5))
True

graphcalc.graphs.invariants.core_invariants.clique_core_number(G)

Compute the clique core number of a graph \(G\): the size of the clique core.

If \(\operatorname{core}_\omega(G)\) denotes the intersection of all maximum cliques of \(G\), this function returns its cardinality:

\[|\operatorname{core}_\omega(G)| \;=\; \left|\bigcap \{\, C \subseteq V(G) : C \text{ is a clique and } |C|=\omega(G)\,\}\right|.\]

Parameters:

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

Returns:

The number of vertices that appear in every maximum clique of \(G\). Returns 0 if \(G\) has no vertices or if the clique core is empty.

Return type:

int

Notes

This quantity can be interpreted as a robustness measure for maximum cliques: it counts how many vertices are unavoidable in any maximum clique.

Complexity

Same as clique_core_set(), since this is a thin wrapper.

See also

clique_core_set

Returns the clique core set itself.

graphcalc.graphs.invariants.core_invariants.clique_core_set(G)

Compute the clique core of a graph \(G\): the intersection of all maximum cliques.

Let \(\omega(G)\) denote the clique number of \(G\), i.e., the maximum size of a clique in \(G\). The clique core is the set of vertices that appear in every maximum clique:

\[\operatorname{core}_\omega(G) \;=\; \bigcap \{\, C \subseteq V(G) : C \text{ is a clique in } G \text{ and } |C|=\omega(G)\,\}.\]

Equivalently, \(\operatorname{core}_\omega(G)\) is the set of vertices that are forced to occur in any maximum clique.

Implementation (deletion test)

This implementation uses the standard deletion characterization for the clique number:

\[v \in \operatorname{core}_\omega(G) \iff \omega(G - v) < \omega(G),\]

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

Justification: if \(\omega(G-v)=\omega(G)\), then \(G-v\) has a maximum clique of size \(\omega(G)\) that avoids \(v\), so \(v\) is not in the intersection. Conversely, if deleting \(v\) reduces \(\omega\), then no maximum clique can avoid \(v\).

param G:

A finite graph. For standard clique semantics, this is intended for simple undirected graphs.

type G:

networkx.Graph-like

returns:

The clique core \(\operatorname{core}_\omega(G)\), i.e., the set of vertices contained in every maximum clique. If \(G\) has no vertices, returns the empty set.

rtype:

set

Notes

• If \(G\) has a unique maximum clique, then the clique core equals that clique.

• If \(G\) has multiple maximum cliques with little overlap, the clique core may be empty.

• Correctness of the deletion test is specific to parameters like \(\omega(G)\) that are realized by vertex subsets in induced subgraphs (a maximum clique of \(G-v\) is also a clique in \(G\) that avoids \(v\)).

Complexity

Performs \(|V(G)|\) calls to gc.clique_number on graphs with one vertex deleted. The total runtime is therefore dominated by the complexity of computing \(\omega(G)\) in your backend.

See also

clique_core_number

Returns the cardinality \(|\operatorname{core}_\omega(G)|\).

core_set_maximum_fast

Generic deletion-test routine used internally.

graphcalc.graphs.invariants.core_invariants.core_number_maximum_fast(G, f_max)

Compute the maximum core number: the size of the maximum core.

This is the cardinality of the set of vertices that appear in every maximum solution:

\[c_{\max}(G) \;=\; \bigl|\operatorname{Core}_{\max}(G)\bigr|,\]

where \(\operatorname{Core}_{\max}(G)\) is returned by core_set_maximum_fast().

Parameters:

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

• f_max (callable) – A function f_max(G) -> int satisfying the deletion-test equivalence described in core_set_maximum_fast().

Returns:

The size of the maximum core, i.e., the number of vertices forced to appear in every maximum solution. Returns 0 for the empty graph.

Return type:

int

Notes

This is a thin wrapper around core_set_maximum_fast().

Complexity

Same as core_set_maximum_fast().

graphcalc.graphs.invariants.core_invariants.core_number_minimum(G, k_func, is_valid_set)

Compute the minimum core number: the size of the minimum core.

This is the cardinality of the intersection of all minimum-cardinality valid sets:

\[c_{\min}(G) \;=\; \bigl|\operatorname{Core}_{\min}(G)\bigr|,\]

where \(\operatorname{Core}_{\min}(G)\) is returned by core_set_minimum().

Parameters:

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

• k_func (callable) – A function k_func(G) -> int returning the optimal minimum size \(k(G)\) for the chosen property.

• is_valid_set (callable) – A predicate is_valid_set(G, S) -> bool deciding validity of a candidate vertex set.

Returns:

The size of the minimum core, i.e. the number of vertices that appear in every minimum solution. Returns 0 for the empty graph, and also returns 0 when \(k(G)=0\).

Return type:

int

Notes

This is a thin wrapper around core_set_minimum().

Complexity

Same as core_set_minimum().

graphcalc.graphs.invariants.core_invariants.core_set_maximum_fast(G, f_max)

Compute the maximum core (intersection of all maximum solutions) via vertex-deletion tests.

Many maximization parameters are defined as the optimum value attained by some vertex subset (e.g., maximum independent set, maximum clique). For such parameters, one can often detect whether a vertex is forced to appear in every maximum solution by checking whether deleting that vertex decreases the optimum.

This function returns the set of vertices that belong to every maximum solution, under the following (crucial) assumption:

Assumption (vertex-forcing by deletion)

For the parameter value

\[M(G) \;=\; f_{\max}(G),\]

the following equivalence holds for every vertex \(v \in V(G)\):

\[v \text{ belongs to every maximum solution } \iff f_{\max}(G - v) < f_{\max}(G),\]

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

Intuition: - If deleting \(v\) does not decrease the optimum value, then there exists an optimal solution contained entirely in \(V(G)\setminus\{v\}\); hence \(v\) is not forced. - If deleting \(v\) does decrease the optimum value, then no optimal solution can avoid \(v\), so \(v\) lies in the intersection of all optimal solutions.

For example, this equivalence holds for: - \(\alpha(G)\) (maximum independent set size): if \(\alpha(G-v) = \alpha(G)\), then there is a maximum independent set avoiding \(v\). - \(\omega(G)\) (maximum clique size): if \(\omega(G-v) = \omega(G)\), then there is a maximum clique avoiding \(v\).

param G:

A finite graph.

type G:

networkx.Graph-like

param f_max:

A function f_max(G) -> int returning a maximization optimum value. Typical examples include gc.independence_number (for \(\alpha\)) or gc.clique_number (for \(\omega\)).

The correctness of this routine depends on f_max satisfying the vertex-forcing by deletion equivalence stated above.

type f_max:

callable

returns:

The maximum core:

\[\operatorname{Core}_{\max}(G) \;=\; \bigcap\{\, S \subseteq V(G) : S \text{ is a maximum solution for } f_{\max} \,\},\]

i.e., the set of vertices that appear in every maximum solution.

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

rtype:

set

Notes

• This method is exact provided the stated equivalence holds for your parameter. It is not valid for arbitrary maximization invariants, especially those not realized by vertex subsets in a straightforward induced-subgraph way.

• Compared to enumerating all maximum solutions, this is typically much faster: it performs one deletion test per vertex.

Complexity

The function performs \(|V(G)|\) evaluations of f_max on induced subgraphs with one vertex deleted. Thus, the total time is dominated by:

\[O\!\left(|V(G)| \cdot T_{f_{\max}}(|V(G)|-1, |E(G-v)|)\right),\]

where \(T_{f_{\max}}\) is the time needed to compute f_max on a graph. The additional overhead from forming induced subgraphs is typically \(O(|V|+|E|)\) per vertex (depending on graph representation).

graphcalc.graphs.invariants.core_invariants.core_set_minimum(G, k_func, is_valid_set)

Compute the minimum core: the intersection of all optimal (minimum-cardinality) valid sets.

Many graph parameters are defined as the minimum size of a vertex set satisfying some property. Examples include dominating sets, zero forcing sets, feedback vertex sets, etc. This function takes such a property (via a membership oracle) and returns the set of vertices that appear in every minimum-size solution.

Formal definition

Let \(P\) be a property of vertex subsets (e.g., “is a dominating set”), and suppose \(k(G)\) is the minimum cardinality of a set satisfying \(P\):

\[k(G) \;=\; \min\{\, |S| : S \subseteq V(G),\ P(G,S)\,\}.\]

The minimum core (sometimes called the core of minimum solutions) is

\[\operatorname{Core}_{\min}(G) \;=\; \bigcap\{\, S \subseteq V(G) : P(G,S)\ \text{and}\ |S|=k(G)\,\}.\]

Intuitively, \(\operatorname{Core}_{\min}(G)\) is the set of vertices that are forced to occur in every optimal solution.

param G:

A finite graph.

type G:

networkx.Graph-like

param k_func:

A function k_func(G) -> int returning the optimal minimum size \(k(G)\). Typical examples are gc.domination_number or gc.zero_forcing_number.

type k_func:

callable

param is_valid_set:

A predicate is_valid_set(G, S) -> bool that decides the property \(P(G,S)\), where S is an iterable of vertices (e.g. a tuple from combinations).

Important: is_valid_set should interpret S as a vertex subset; it should not depend on order or multiplicity.

type is_valid_set:

callable

returns:

The set \(\operatorname{Core}_{\min}(G)\).

Conventions: - If \(|V(G)|=0\), returns the empty set. - If \(k(G)=0\), returns the empty set (since the empty set is a minimum solution, and the intersection over the family of minimum solutions is empty). - If the running intersection becomes empty during enumeration, the function returns early.

If no valid set of size \(k(G)\) is found (which indicates an inconsistency between k_func and is_valid_set), this implementation returns the empty set.

rtype:

set

raises ValueError:

If k_func(G) does not return an integer, or returns a value outside \([0, |V(G)|]\).

Notes

• Exact brute force. This routine enumerates all \(k\)-subsets of \(V(G)\) and tests validity. It is intended only for small graphs and/or small \(k\).

• Correctness depends on consistency: k_func must return the true minimum size for the property tested by is_valid_set. If they disagree, the output is not meaningful.

Complexity

Let \(n=|V(G)|\) and \(k=k(G)\). In the worst case, the function performs \(\binom{n}{k}\) calls to is_valid_set. Thus the runtime is exponential in \(n\) in general, and also depends on the cost of the validity test itself.

graphcalc.graphs.invariants.core_invariants.domination_core_number(G)

Compute the domination core number of a graph \(G\): the size of the domination core.

If \(\operatorname{core}_\gamma(G)\) denotes the intersection of all minimum dominating sets of \(G\), this function returns its cardinality:

\[|\operatorname{core}_\gamma(G)| \;=\; \left|\bigcap \{\, S \subseteq V(G) : S \text{ is dominating and } |S|=\gamma(G)\,\}\right|.\]

Parameters:

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

Returns:

The number of vertices that appear in every minimum dominating set of \(G\). Returns 0 if \(G\) is empty or if the domination core is empty.

Return type:

int

Notes

This is a thin wrapper around domination_core_set().

Complexity

Same as domination_core_set(), since this function simply takes the set cardinality.

See also

domination_core_set

Returns the domination core set itself.

graphcalc.graphs.invariants.core_invariants.domination_core_set(G)

Compute the domination core of a graph \(G\): the intersection of all minimum dominating sets.

Let \(\gamma(G)\) denote the domination number of \(G\), i.e., the minimum size of a dominating set. The domination core is the set of vertices that appear in every minimum dominating set:

\[\operatorname{core}_\gamma(G) \;=\; \bigcap \{\, S \subseteq V(G) : S \text{ is dominating in } G \text{ and } |S|=\gamma(G)\,\}.\]

Equivalently, \(\operatorname{core}_\gamma(G)\) is the set of vertices that are forced to occur in any minimum dominating set.

A set \(S \subseteq V(G)\) is dominating if every vertex of \(G\) is in \(S\) or has a neighbor in \(S\), i.e., \(N[S]=V(G)\).

Parameters:

G (networkx.Graph-like) – A finite graph. This is intended primarily for simple undirected graphs under the standard adjacency notion.

Returns:

• set – The domination core \(\operatorname{core}_\gamma(G)\).

• Conventions

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

• • If \(\gamma(G)=0\) (which occurs only for the empty graph under standard conventions), returns the empty set.

• - If the intersection of all minimum dominating sets is empty, returns the empty set.

Notes

• This function delegates to core_set_minimum() using: k_func = gc.domination_number and is_valid_set = gc.is_dominating_set.

• The implementation is exact but may be expensive: it enumerates all \(\gamma(G)\)-subsets of \(V(G)\) and tests which ones are dominating.

Complexity

Let \(n=|V(G)|\) and \(k=\gamma(G)\). In the worst case, the function performs \(\binom{n}{k}\) dominance checks, so the runtime is exponential in \(n\) in general (and depends on the cost of gc.is_dominating_set).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # In a star, every minimum dominating set is {center}, so the domination core is {center}.
>>> G = nx.star_graph(4)
>>> gc.domination_core_set(G) == {0}
True

graphcalc.graphs.invariants.core_invariants.zero_forcing_core_number(G)

Compute the zero forcing core number of a graph \(G\): the size of the zero forcing core.

If \(\operatorname{core}_Z(G)\) denotes the intersection of all minimum zero forcing sets of \(G\), this function returns its cardinality:

\[|\operatorname{core}_Z(G)| \;=\; \left|\bigcap \{\, S \subseteq V(G) : S \text{ is zero forcing and } |S|=Z(G)\,\}\right|.\]

Parameters:

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

Returns:

The number of vertices that appear in every minimum zero forcing set of \(G\). Returns 0 if \(G\) is empty or if the zero forcing core is empty.

Return type:

int

Notes

This is a thin wrapper around zero_forcing_core_set().

Complexity

Same as zero_forcing_core_set().

See also

zero_forcing_core_set

Returns the zero forcing core set itself.

graphcalc.graphs.invariants.core_invariants.zero_forcing_core_set(G)

Compute the zero forcing core of a graph \(G\): the intersection of all minimum zero forcing sets.

Let \(Z(G)\) denote the zero forcing number of \(G\), i.e., the minimum size of a zero forcing set under the standard zero forcing rule. The zero forcing core is the set of vertices that appear in every minimum zero forcing set:

\[\operatorname{core}_Z(G) \;=\; \bigcap \{\, S \subseteq V(G) : S \text{ is zero forcing in } G \text{ and } |S|=Z(G)\,\}.\]

Equivalently, \(\operatorname{core}_Z(G)\) is the set of vertices that are forced to occur in any minimum zero forcing set.

Zero forcing (brief definition)

Start with a set \(S\) of initially colored vertices. Repeatedly apply the color-change rule: a colored vertex with exactly one uncolored neighbor forces that neighbor to become colored. A set \(S\) is a zero forcing set if this process eventually colors all vertices. The zero forcing number \(Z(G)\) is the minimum size of such a set.

param G:

A finite graph. This is intended primarily for simple undirected graphs under the standard adjacency notion.

type G:

networkx.Graph-like

returns:

The zero forcing core \(\operatorname{core}_Z(G)\).

Conventions: - If \(|V(G)|=0\), returns the empty set. - If \(Z(G)=0\) (which occurs only for the empty graph under standard conventions), returns the empty set. - If the intersection of all minimum zero forcing sets is empty, returns the empty set.

rtype:

set

Notes

• This function delegates to core_set_minimum() using:

  • k_func = gc.zero_forcing_number and

  • is_valid_set = gc.is_zero_forcing_set.

• The implementation is exact but may be expensive: it enumerates all \(Z(G)\)-subsets of \(V(G)\) and tests which ones are zero forcing.

Complexity

Let \(n=|V(G)|\) and \(k=Z(G)\). In the worst case, the function performs \(\binom{n}{k}\) zero-forcing checks, so the runtime is exponential in \(n\) in general (and depends on the cost of gc.is_zero_forcing_set).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # In a path, there are minimum zero forcing sets of size 1 (either endpoint),
>>> # so the intersection is empty.
>>> G = nx.path_graph(6)
>>> gc.zero_forcing_core_set(G)
set()