transversal invariants

Transversal Invariants

graphcalc.graphs.invariants.transversal_invariants.maximal_clique_transversal_number(G)[source]

Compute the maximal-clique transversal number of \(G\).

A maximal-clique transversal is a set \(S \subseteq V(G)\) that intersects every maximal clique of \(G\). Equivalently, if \(\mathcal{C}\) is the family of maximal cliques of \(G\), then \(S\) is feasible iff \(S \cap C \neq \varnothing\) for all \(C \in \mathcal{C}\).

This function returns the minimum possible size: \(\tau_{\max\mathrm{clique}}(G) = \min\{ |S| : S \cap C \neq \varnothing \;\; \forall C \in \mathcal{C}\}\).

Parameters:

G (networkx.Graph) – The input graph (intended for finite simple undirected graphs).

Notes

This is an exact brute-force hitting-set computation:

  1. Enumerate maximal cliques using networkx.find_cliques().

  2. Search subsets \(S \subseteq V(G)\) in increasing cardinality until one intersects every maximal clique.

Conventions: - If \(|V(G)| = 0\), returns 0. - For an edgeless graph on \(n\) vertices, returns \(n\) (each vertex is a maximal clique).

Complexity can be exponential in \(n\) (both the number of maximal cliques and the subset search). Intended only for small graphs.

Returns:

The minimum size of a vertex set that meets every maximal clique of \(G\).

Return type:

int

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.complete_graph(4)
>>> gc.maximal_clique_transversal_number(G)
1
>>> H = nx.empty_graph(5)
>>> gc.maximal_clique_transversal_number(H)
5
graphcalc.graphs.invariants.transversal_invariants.maximal_independent_set_transversal_number(G)[source]

Compute the maximal-independent-set transversal number of \(G\).

A set \(S \subseteq V(G)\) is a transversal of maximal independent sets if it intersects every maximal independent set \(I\) of \(G\), i.e., \(S \cap I \neq \varnothing\) for all maximal independent sets \(I\).

This function returns the minimum possible size of such a set.

Notes

Maximal independent sets of \(G\) are exactly maximal cliques of the complement graph \(\overline{G}\). Therefore, \(\tau_{\max\mathrm{ind}}(G) = \tau_{\max\mathrm{clique}}(\overline{G})\), and this function delegates to maximal_clique_transversal_number(nx.complement(G)).

Conventions: - If \(|V(G)| = 0\), returns 0. - For a complete graph \(K_n\), every maximal independent set is a singleton, so the answer is \(n\).

Parameters:

G (networkx.Graph) – The input graph (intended for finite simple undirected graphs).

Returns:

The minimum size of a vertex set intersecting every maximal independent set of \(G\).

Return type:

int

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.complete_graph(4)
>>> gc.maximal_independent_set_transversal_number(G)
4
>>> H = nx.empty_graph(5)
>>> gc.maximal_independent_set_transversal_number(H)
1
graphcalc.graphs.invariants.transversal_invariants.minimal_dominating_set_transversal_number(G, max_n=20)[source]

Compute the minimal-dominating-set transversal number of \(G\).

Let \(\mathcal{D}\) be the family of all inclusion-minimal dominating sets of \(G\). A set \(S \subseteq V(G)\) is a transversal (hitting set) for \(\mathcal{D}\) if \(S \cap D \neq \varnothing\) for all \(D \in \mathcal{D}\).

This function returns the minimum possible size: \(\tau_{\min\mathrm{dom}}(G) = \min\{ |S| : S \cap D \neq \varnothing \;\; \forall D \in \mathcal{D}\}\).

Parameters:

  • G (networkx.Graph) – The input graph (intended for finite simple undirected graphs).

  • max_n (int, default=20) – Safety cutoff on \(|V(G)|\). This routine enumerates all inclusion-minimal dominating sets and then solves a hitting-set problem over \(V(G)\), both of which can be exponential.

Notes

Exact brute force:

  1. Enumerate all inclusion-minimal dominating sets \(\mathcal{D}\).

  2. Search subsets \(S \subseteq V(G)\) in increasing cardinality until one intersects every \(D \in \mathcal{D}\).

Conventions: - If \(|V(G)| = 0\), returns 0. - If \(|V(G)| > 0\), then \(\mathcal{D}\) is nonempty, so the answer is at least 1.

Returns:

The minimum size of a vertex set intersecting every inclusion-minimal dominating set of \(G\).

Return type:

int

Raises:

ValueError – If \(|V(G)| > \texttt{max_n}\).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.complete_graph(4)
>>> gc.minimal_dominating_set_transversal_number(G)
4
>>> H = nx.star_graph(5)
>>> gc.minimal_dominating_set_transversal_number(H)
2