classics

Classics

graphcalc.graphs.invariants.classics.arboricity(G: Graph) → int

Compute the (undirected) arboricity \(a(G)\) exactly.

Arboricity measures how many forests are needed to cover the edges of a graph. Formally, \(a(G)\) is the minimum integer \(k\) such that \(E(G)\) can be partitioned into \(k\) forests.

Nash–Williams / Tutte characterization

A classical theorem gives the exact formula

\[a(G) \;=\; \max_{H \subseteq G,\; |V(H)| \ge 2}\; \left\lceil \frac{|E(H)|}{|V(H)| - 1} \right\rceil.\]

Equivalently, \(a(G)\) is the smallest \(k\) such that for every vertex subset \(S \subseteq V(G)\) with \(|S| \ge 2\),

\[|E(G[S])| \;\le\; k\,(|S| - 1).\]

This function computes arboricity exactly by testing candidate values of \(k\) via a min-cut reduction that detects whether there exists a violating subset \(S\) with

\[|E(G[S])| \;>\; k\,(|S| - 1).\]

Min-cut oracle

For a fixed \(k\), consider the objective

\[\max_{S \subseteq V(G)} \bigl(|E(G[S])| - k|S|\bigr).\]

Since \(|E(G[S])| - k(|S|-1) = (|E(G[S])| - k|S|) + k\), a violation exists if and only if

\[\max_{S} \bigl(|E(G[S])| - k|S|\bigr) \;>\; -k.\]

This maximum can be obtained via an \(s\)–\(t\) min-cut construction:

• Create a node for each original vertex (V-nodes).

• Create a node for each original edge (E-nodes).

• Add an arc source -> E-node with capacity 1.

• Add arcs E-node -> its two endpoint V-nodes with capacity INF.

• Add an arc V-node -> sink with capacity \(k\).

If the \(s\)-side contains a vertex subset \(S\), then the cut value is

\[\text{cut} \;=\; m - |E(G[S])| + k|S|,\]

so minimizing the cut is equivalent to maximizing \(|E(G[S])| - k|S|\).

param G:

An undirected graph. Self-loops are ignored. For a MultiGraph, parallel edges increase \(|E(G[S])|\); if you want multigraph arboricity, be explicit about the convention or pass a simple projection.

type G:

networkx.Graph

returns:

The exact arboricity \(a(G)\).

rtype:

int

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> gc.arboricity(nx.path_graph(10))
1
>>> gc.arboricity(nx.complete_graph(6))
3
>>> gc.arboricity(nx.complete_bipartite_graph(3, 4))
2

graphcalc.graphs.invariants.classics.average_distance(G)

Compute the average finite shortest-path distance of an undirected graph.

This function returns the mean of the unweighted shortest-path distance \(d_G(u,v)\) over all unordered vertex pairs \(\{u,v\}\) for which the distance is finite (i.e., \(u\) and \(v\) lie in the same connected component). Formally, let

\[P \;=\; \bigl\{ \{u,v\} \subseteq V(G) : u \neq v,\ d_G(u,v) < \infty \bigr\},\]

then the returned value is

\[\begin{split}\operatorname{avgdist}(G) \;=\; \begin{cases} \dfrac{1}{|P|}\sum_{\{u,v\}\in P} d_G(u,v), & |P|>0,\\[6pt] 0, & |P|=0. \end{cases}\end{split}\]

Conventions

• If \(|V(G)| < 2\), the function returns 0.0.

• If \(G\) is disconnected, only pairs of vertices within the same connected component are included; pairs in different components are ignored (they are not treated as having infinite distance).

• With these conventions, the only way \(|P|=0\) is when \(|V(G)|<2\).

param G:

A finite undirected graph. Distances are computed as unweighted shortest-path lengths (BFS distances). If you require weighted distances, use Dijkstra-based routines (e.g. nx.single_source_dijkstra_path_length) and adjust the definition accordingly.

type G:

networkx.Graph-like

returns:

The average finite shortest-path distance over all connected unordered vertex pairs.

rtype:

float

Notes

• For a connected graph, this equals the standard average shortest-path length (also called the mean distance).

• Some authors define the average distance only for connected graphs (and otherwise return \(\infty\) or raise an exception). This implementation instead computes an intra-component mean, which stays finite on disconnected graphs.

Complexity

Let the connected components of \(G\) be \(C_1,\dots,C_t\). The implementation runs a BFS from each vertex within each component and counts each unordered pair once. The time complexity is

\[O\!\left(\sum_{i=1}^t |V(C_i)|\bigl(|V(C_i)| + |E(C_i)|\bigr)\right),\]

and the additional memory used by each BFS is \(O(|V(C_i)|)\).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # Path on 4 vertices: distances are 1,2,3,1,2,1 (sum 10 over 6 pairs)
>>> G = nx.path_graph(4)
>>> gc.average_distance(G)
1.6666666666666667

>>> # Disconnected: average over pairs within components only
>>> H = nx.disjoint_union(nx.path_graph(3), nx.path_graph(2))
>>> gc.average_distance(H)
1.25

graphcalc.graphs.invariants.classics.bipartite_number(G: Graph, **solver_kwargs) → int

Compute the bipartite number of a graph \(G\).

The bipartite number \(b(G)\) is the order of a largest induced bipartite subgraph of \(G\). Equivalently,

\[b(G) = \max\{\, |S| : S \subseteq V(G)\ \text{and}\ G[S]\ \text{is bipartite}\,\}.\]

Since bipartite graphs are exactly the graphs whose vertices can be partitioned into two independent sets, this implementation formulates the problem as a mixed integer linear program and solves it exactly.

Notes

This function calls maximum_induced_bipartite_subgraph() and returns the size of the selected vertex set.

The bipartite number is complementary to the odd cycle transversal number \(\tau_{\mathrm{odd}}(G)\):

\[b(G) = |V(G)| - \tau_{\mathrm{odd}}(G).\]

Parameters:

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

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Flexible solver specification handled by graphcalc.solvers.with_solver().

• solver_options (dict, optional) – Extra keyword arguments when constructing the solver if needed.

• verbose (bool, default=False) – Passed through to the solver wrapper.

Returns:

The bipartite number \(b(G)\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph, complete_graph
>>> gc.bipartite_number(cycle_graph(5))
4
>>> gc.bipartite_number(complete_graph(4))
2

graphcalc.graphs.invariants.classics.chromatic_number(G: Graph) → int

The chromatic number of a graph is the smallest number of colors needed to color the vertices of \(G\) so that no two adjacent vertices share the same color.

Parameters:

G (NetworkX Graph or GraphCalc SimpleGraph) – An undirected graph.

Returns:

The chromatic number of \(G\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph
>>> G = complete_graph(4)
>>> gc.chromatic_number(G)
4

graphcalc.graphs.invariants.classics.clique_number(G: Graph, **solver_kwargs) → int

Compute the clique number \(\omega(G)\).

A clique in \(G=(V,E)\) is a subset \(C \subseteq V\) such that every pair of vertices in \(C\) is adjacent. The clique number is

\[\omega(G) = \max \{ |C| : C \subseteq V, \, C \text{ induces a clique} \}.\]

Notes

• NP-hard in general.

• This implementation calls maximum_clique(), which solves a MIP.

• Relations: - Complement: \(\omega(G) = \alpha(\overline{G})\). - Trivial bound: \(\omega(G) \le \Delta(G)+1\).

Parameters:

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

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Same solver options as maximum_clique().

• solver_options (dict, optional) – Extra keyword arguments used when constructing the solver if needed.

Returns:

The clique number \(\omega(G)\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph, cycle_graph
>>> gc.clique_number(complete_graph(4))
4
>>> gc.clique_number(cycle_graph(5))
2

graphcalc.graphs.invariants.classics.edge_cover_number(G: Graph) → int

Return the size of a smallest edge cover in the graph \(G\).

Parameters:

G (NetworkX Graph or GraphCalc SimpleGraph) – An undirected graph.

Returns:

The size of a smallest edge cover of \(G\).

Return type:

number

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph
>>> G = complete_graph(4)
>>> gc.edge_cover_number(G)
2

graphcalc.graphs.invariants.classics.independence_number(G: Graph, **solver_kwargs) → int

Return the size of a largest independent set in G.

An independent set in a graph \(G=(V,E)\) is a subset \(S \subseteq V\) such that no two vertices in \(S\) are adjacent. The independence number \(\alpha(G)\) is defined as

\[\alpha(G) = \max \{ |S| : S \subseteq V, \, S \text{ is independent} \}.\]

Notes

• The independence number is NP-hard to compute in general.

• This implementation calls maximum_independent_set(), which formulates the problem as a mixed integer program (MIP).

• Relations:

  • Complement: \(\alpha(G) = \omega(\overline{G})\).

  • Bound: \(\alpha(G) \ge \frac{|V|}{\Delta(G)+1}\) (Caro–Wei).

Parameters:

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

• verbose (bool, default=False) – Passed through to the solver via graphcalc.solvers.with_solver().

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Flexible solver spec handled by graphcalc.solvers.resolve_solver().

• solver_options (dict, optional) – Extra kwargs used when constructing the solver if needed.

Returns:

The independence number \(\alpha(G)\) of the graph.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph, cycle_graph
>>> gc.independence_number(complete_graph(4))
1
>>> gc.independence_number(cycle_graph(5))
2

graphcalc.graphs.invariants.classics.is_hamiltonian(G: Graph) → bool

Return True iff the undirected simple graph G has a Hamiltonian cycle.

This is an exact exponential-time backtracking algorithm, so it is only practical for small to medium graphs.

Parameters:

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

Returns:

True if G is Hamiltonian, else False.

Return type:

bool

graphcalc.graphs.invariants.classics.linear_arboricity(G: Graph) → int

Compute the linear arboricity \(\mathrm{la}(G)\) exactly (intended for small simple graphs).

A linear forest is a forest whose connected components are paths (including isolated vertices). Equivalently, a graph is a linear forest if and only if it is acyclic and has maximum degree at most 2.

The linear arboricity \(\mathrm{la}(G)\) is the minimum integer \(k\) such that the edge set can be partitioned into \(k\) linear forests.

\[\mathrm{la}(G) \;=\; \min\{\, k : E(G)=E(L_1)\,\dot\cup\,\cdots\,\dot\cup\,E(L_k)\ \text{with each } L_i \text{ a linear forest}\,\}.\]

Exactness and search strategy

Computing linear arboricity is NP-hard in general. This implementation is intended for small graphs (typically \(n \le 20\text{--}30\)) and performs an exact incremental feasibility search:

• Lower bound: \(\lceil \Delta(G)/2 \rceil\), since in any linear forest each vertex has degree at most 2, so across \(k\) forests a vertex can support at most \(2k\) incident edges.

• Upper bound: \(|E(G)|\), since assigning each edge its own color class yields a linear forest.

For each \(k\) from the lower bound upward, the algorithm attempts to assign each edge one of \(k\) colors so that each color class induces a linear forest. The first feasible \(k\) is returned.

Feasibility checking (fixed k)

Backtracking assigns edges to colors subject to:

• Per-color degree constraint: for every color class and vertex, degree is at most 2.

• Per-color acyclicity: adding an edge may not create a cycle in that color class. This is enforced via a rollback disjoint-set union (DSU) structure per color.

param G:

Undirected graph. This routine is intended for simple graphs. Self-loops are ignored.

Note: if a MultiGraph is provided, it is first projected to a simple graph via nx.Graph(G), which collapses parallel edges; thus multiplicity is not preserved under this implementation.

type G:

nx.Graph

returns:

• int – The exact linear arboricity \(\mathrm{la}(G)\) (under the above conventions). Returns 0 if \(|E(G)|=0\).

• Complexity

• ———-

• Exponential in \(|E(G)|\) in the worst case due to backtracking; practical only for small graphs.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> gc.linear_arboricity(nx.path_graph(10))
1
>>> gc.linear_arboricity(nx.cycle_graph(10))
2

graphcalc.graphs.invariants.classics.matching_number(G: Graph, **solver_kwargs) → int

Return the size of a maximum matching in \(G\).

Parameters:

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

• verbose (bool, default=False) – Passed through to the solver.

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Flexible solver spec handled by graphcalc.solvers.resolve_solver().

• solver_options (dict, optional) – Extra kwargs used when constructing the solver if needed.

Returns:

The matching number \(\nu(G)\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph
>>> gc.matching_number(complete_graph(4))
2

graphcalc.graphs.invariants.classics.maximum_clique(G: Graph, *, verbose: bool = False, solve=None) → Set[Hashable]

Return a maximum clique of nodes in G using integer programming.

We choose binary variables \(x_v \in \{0,1\}\) for each vertex \(v\), maximize the selected vertices, and forbid selecting non-adjacent pairs:

Objective

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

Constraints

\[x_u + x_v \le 1 \quad \text{for every non-edge } \{u,v\} \notin E,\]

which ensures the chosen vertices induce a clique.

param G:

An undirected simple graph.

type G:

networkx.Graph or graphcalc.SimpleGraph

param verbose:

If True, print solver output (when supported) and intermediate details.

type verbose:

bool, default=False

param solver:

Specification of the solver backend. Same accepted forms as in maximum_independent_set(). If None, uses get_default_solver().

type solver:

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

param solver_options:

Extra keyword arguments when constructing the solver if solver is a string or class. Ignored if solver is an existing object.

type solver_options:

dict, optional

returns:

A set of nodes forming a maximum clique in G.

rtype:

set of hashable

raises ValueError:

If no optimal solution is found by the solver.

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph
>>> gc.maximum_clique(complete_graph(4)) == {0, 1, 2, 3}
True

Optionally specify a solver (skipped in doctest since availability varies):

>>> from pulp import HiGHS_CMD
>>> gc.maximum_clique(complete_graph(4), solver=HiGHS_CMD)
{0, 1, 2, 3}

graphcalc.graphs.invariants.classics.maximum_independent_set(G: Graph, *, verbose: bool = False, solve=None) → Set[Hashable]

Return a largest independent set of nodes in G.

This method formulates the maximum independent set problem as an integer linear program:

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

subject to

\[x_u + x_v \leq 1 \quad \text{for all } \{u, v\} \in E,\]

where E and V are the edge and vertex sets of G, and \(x_v \in \{0,1\}\) for each vertex.

Parameters:

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

• verbose (bool, default=False) – If True, print solver output (when supported) and intermediate results during optimization. If False, run silently.

Notes

This function also accepts the standard solver kwargs provided by graphcalc.solvers.with_solver(), e.g. solver="highs" or solver={"name":"GUROBI_CMD","options":{"timeLimit":10}}.

Returns:

A set of nodes comprising a largest independent set in G.

Return type:

set of hashable

Raises:

ValueError – If no optimal solution is found by the solver.

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph
>>> G = complete_graph(4)
>>> S = gc.maximum_independent_set(G)
>>> len(S)
1
>>> # Optionally choose a specific solver
>>> S = gc.maximum_independent_set(G, solver="cbc")
>>> len(S)
1

graphcalc.graphs.invariants.classics.maximum_induced_bipartite_subgraph(G: Graph, *, verbose: bool = False, solve=None) → Set[Hashable]

Return a maximum-cardinality vertex set inducing a bipartite subgraph of G.

The bipartite number of a graph \(G=(V,E)\) is the maximum order of an induced bipartite subgraph. Equivalently, it is the largest size of a subset \(S \subseteq V\) such that \(G[S]\) is bipartite.

This function computes such a subset exactly using a mixed integer linear program.

Formulation

For each vertex \(v \in V\), introduce binary variables \(a_v, b_v \in \{0,1\}\) where:

• \(a_v = 1\) means v is selected and placed in part A,

• \(b_v = 1\) means v is selected and placed in part B.

We maximize the number of selected vertices:

\[\max \sum_{v \in V} (a_v + b_v)\]

subject to:

\[a_v + b_v \le 1 \qquad \text{for all } v \in V,\]

and for each edge \(uv \in E\),

\[a_u + a_v \le 1, \qquad b_u + b_v \le 1.\]

These constraints ensure that the selected vertices induce a graph whose vertex set can be partitioned into two independent sets, hence an induced bipartite subgraph.

param G:

An undirected simple graph.

type G:

networkx.Graph or graphcalc.SimpleGraph

param verbose:

If True, print solver output when supported.

type verbose:

bool, default=False

param solver:

Flexible solver specification handled by graphcalc.solvers.with_solver().

type solver:

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

param solver_options:

Extra keyword arguments when constructing the solver if needed.

type solver_options:

dict, optional

returns:

A maximum-cardinality subset of vertices inducing a bipartite subgraph.

rtype:

set of hashable

raises ValueError:

If no optimal solution is found by the solver.

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(5)
>>> S = gc.maximum_induced_bipartite_subgraph(G)
>>> len(S)
4

>>> from graphcalc.graphs.generators import complete_graph
>>> H = complete_graph(4)
>>> len(gc.maximum_induced_bipartite_subgraph(H))
2

graphcalc.graphs.invariants.classics.maximum_matching(G: Graph, *, verbose: bool = False, solve=None) → Set[Tuple[Hashable, Hashable]]

Return a maximum matching in \(G\) via integer programming.

A matching is a set of edges with no shared endpoint. We solve:

\[\max \sum_{e \in E} x_e \quad \text{s.t. } \sum_{e \in \delta(v)} x_e \le 1 \;\; \forall v\in V,\; x_e \in \{0,1\}.\]

Parameters:

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

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

Notes

This function accepts the standard solver kwargs provided by graphcalc.solvers.with_solver(), e.g. solver="highs" or solver={"name":"GUROBI_CMD","options":{"timeLimit":10}}.

Returns:

A maximum matching as a set of edges (u, v).

Return type:

set of tuple

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> M = gc.maximum_matching(G)
>>> len(M)
2

graphcalc.graphs.invariants.classics.minimum_edge_cover(G: Graph)

Return a smallest edge cover of the graph \(G\).

Parameters:

G (NetworkX Graph or GraphCalc SimpleGraph) – An undirected graph.

Returns:

A smallest edge cover of \(G\).

Return type:

set

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph
>>> G = complete_graph(4)
>>> solution = gc.minimum_edge_cover(G)

graphcalc.graphs.invariants.classics.minimum_vertex_cover(G: Graph, **solver_kwargs) → Set[Hashable]

Return a smallest vertex cover of \(G\).

A set \(X \subseteq V\) is a vertex cover if every edge has at least one endpoint in \(X\). By complementarity with independent sets, a smallest vertex cover has size \(|V| - \alpha(G)\) and equals \(V \setminus S\) for any maximum independent set \(S\).

Parameters:

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

• verbose (bool, default=False) – Passed through to the solver used by maximum_independent_set().

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Flexible solver spec handled by graphcalc.solvers.resolve_solver().

• solver_options (dict, optional) – Extra kwargs used when constructing the solver if needed.

Returns:

A smallest vertex cover of \(G\).

Return type:

set of hashable

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph
>>> G = complete_graph(4)
>>> len(gc.minimum_vertex_cover(G))  # any 3 vertices form a minimum cover
3

graphcalc.graphs.invariants.classics.optimal_proper_coloring(G: Graph) → Dict

Finds the optimal proper coloring of a graph using linear programming.

This function uses integer linear programming to find the optimal (minimum) number of colors required to color the graph \(G\) such that no two adjacent nodes have the same color. Each node is assigned a color represented by a binary variable.

Parameters:

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

Returns:

A dictionary where keys are color indices and values are lists of nodes in \(G\) assigned that color.

Return type:

dict

Examples

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

>>> G = complete_graph(4)
>>> coloring = gc.optimal_proper_coloring(G)

graphcalc.graphs.invariants.classics.path_cover_number(G, max_n=20)

Compute the path cover number of an undirected graph: the minimum size of a vertex-disjoint path cover.

This function solves the following optimization problem. Find the smallest integer \(k\) for which there exist pairwise vertex-disjoint simple paths \(P_1,\dots,P_k\) in \(G\) such that their vertex sets partition the vertex set:

\[V(G) \;=\; V(P_1)\,\dot\cup\,V(P_2)\,\dot\cup\,\cdots\,\dot\cup\,V(P_k),\]

where each \(P_i\) is a simple undirected path (and paths of length 0, i.e. single vertices, are allowed).

In other words, this is the minimum number of disjoint paths whose union covers all vertices. This quantity is also called a path partition number in some sources.

Conventions

• Paths are simple undirected paths.

• Singleton paths \(\{v\}\) are allowed (paths of length 0).

• The chosen paths must be vertex-disjoint, so the cover is a partition of \(V(G)\).

• If \(G\) has no vertices, the value is 0.

param G:

Intended for finite undirected graphs (typically simple graphs).

type G:

networkx.Graph-like

param max_n:

Safety cutoff on \(|V(G)|\). This implementation is exact but brute-force and can become infeasible quickly. If \(|V(G)| > \texttt{max_n}\), a ValueError is raised.

type max_n:

int, optional

returns:

The minimum number of vertex-disjoint paths whose union is \(V(G)\).

rtype:

int

raises ValueError:

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

Notes

• This is not the standard “minimum path cover” problem for DAGs (which is polynomial-time via maximum matching). Here the input is an undirected graph and the paths must be vertex-disjoint and cover all vertices; this variant is NP-hard in general.

• Implementation strategy:

  1. Enumerate candidate paths by their vertex sets using _all_simple_paths_vertex_sets().

  2. Backtrack to choose a minimum number of these sets that form a partition of \(V(G)\).

• The backtracking branches on an uncovered vertex \(v\) and tries all candidate path-sets containing \(v\) that fit inside the remaining uncovered vertices.

Complexity

Exponential in \(n = |V(G)|\). The helper that enumerates simple paths can itself be exponential, and the subsequent set-packing/partition backtracking is also exponential. Intended only for small graphs (your cutoff parameter controls this).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> # A path is coverable by a single path
>>> G = nx.path_graph(6)
>>> gc.path_cover_number(G)
1

>>> # An edgeless graph on n vertices needs n singleton paths
>>> H = nx.empty_graph(5)
>>> gc.path_cover_number(H)
5

>>> # Two disjoint paths need two paths in the cover
>>> J = nx.disjoint_union(nx.path_graph(3), nx.path_graph(4))
>>> gc.path_cover_number(J)
2

graphcalc.graphs.invariants.classics.triameter(G: Graph) → int

Compute the triameter of a connected graph \(G\).

The triameter is defined as:

\[\text{max} \{ d(u,v) + d(v,w) + d(u,w) : u, v, w \in V \}\]

where \(d(u,v)\) is the shortest-path distance between \(u\) and \(v\).

Parameters:

G (NetworkX Graph or GraphCalc SimpleGraph) – An undirected, connected graph.

Returns:

The triameter of the graph.

Return type:

int

Examples

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

>>> G = cycle_graph(10)
>>> gc.triameter(G)
10

graphcalc.graphs.invariants.classics.vertex_clique_cover_number(G: Graph) → int

Vertex clique cover number (theta(G)): the fewest cliques needed to partition (V(G)).

Uses (theta(G) = chi(overline{G})), i.e., the chromatic number of the complement.

Parameters:

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

Returns:

The vertex clique cover number (theta(G)).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph, cycle_graph
>>> gc.vertex_clique_cover_number(complete_graph(4))
1
>>> gc.vertex_clique_cover_number(cycle_graph(5))  # C5, complement is C5, χ=3
3

graphcalc.graphs.invariants.classics.vertex_clique_cover_partition(G: Graph) → Dict[int, List[Hashable]]

Partition (V(G)) into the fewest number of cliques (a vertex clique cover), returning the actual parts.

This uses the identity (theta(G) = chi(overline{G})): we compute an optimal proper coloring of the complement (overline{G}), then interpret each color class as a clique in (G).

Parameters:

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

Returns:

A dictionary mapping color indices to vertex lists. Only nonempty parts are returned. Each part induces a clique in (G).

Return type:

dict[int, list[hashable]]

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(5)  # C5
>>> parts = gc.vertex_clique_cover_partition(G)
>>> sum(len(vs) for vs in parts.values()) == G.order()
True

graphcalc.graphs.invariants.classics.vertex_cover_number(G: Graph, **solver_kwargs) → int

Return the size of a smallest vertex cover of \(G\).

Uses \(\tau(G) = |V| - \alpha(G)\).

Parameters:

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

• verbose (bool, default=False) – Passed through to the solver used by independence_number().

• solver (str or dict or pulp.LpSolver or type or callable or None, optional) – Flexible solver spec handled by graphcalc.solvers.resolve_solver().

• solver_options (dict, optional) – Extra kwargs used when constructing the solver if needed.

Returns:

The vertex cover number \(\tau(G)\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph
>>> gc.vertex_cover_number(complete_graph(4))
3