spectral

Spectral

class graphcalc.graphs.invariants.spectral.AdjacencyInertia(positive: int, negative: int, zero: int)

Bases: object

Inertia triple of the adjacency matrix of a graph.

For a graph \(G\), let \(A(G)\) be its adjacency matrix. The adjacency inertia is the triple

\[(p(G), n(G), z(G)),\]

where:

• \(p(G)\) is the number of positive eigenvalues of \(A(G)\),

• \(n(G)\) is the number of negative eigenvalues of \(A(G)\),

• \(z(G)\) is the number of zero eigenvalues of \(A(G)\).

Since \(A(G)\) is real symmetric for an undirected graph, these counts are well-defined over the real numbers and satisfy

\[p(G) + n(G) + z(G) = |V(G)|.\]

Parameters:

• positive (int) – The number of positive adjacency eigenvalues.

• negative (int) – The number of negative adjacency eigenvalues.

• zero (int) – The number of zero adjacency eigenvalues.

negative: int

positive: int

zero: int

graphcalc.graphs.invariants.spectral.adjacency_eigenvalues(G: Graph) → float

Compute the eigenvalues of the adjacency matrix of a graph.

For a graph \(G=(V,E)\) with adjacency matrix \(A(G)\), the adjacency eigenvalues are the roots of the characteristic polynomial

\[\det(\lambda I - A(G)) = 0.\]

These eigenvalues (the spectrum of the graph) encode rich structural information, including connectivity, regularity, and expansion properties.

Parameters:

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

Returns:

The sorted list of real eigenvalues of \(A(G)\).

Return type:

numpy.ndarray

Examples

>>> import numpy as np
>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> eigenvals = gc.adjacency_eigenvalues(G)
>>> np.allclose(eigenvals, [-2.0, 0.0, 0.0, 2.0], atol=1e-6)
True

graphcalc.graphs.invariants.spectral.adjacency_graph_energy(G: Graph) → float

Compute the graph energy of a graph.

For a graph \(G\) with adjacency eigenvalues \(\lambda_1,\dots,\lambda_n\), the graph energy is defined as

\[E(G) = \sum_{i=1}^n |\lambda_i|.\]

This invariant was introduced by Gutman and plays an important role in spectral graph theory and chemical graph theory.

Parameters:

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

Returns:

The graph energy of \(G\).

Return type:

float

Examples

>>> import numpy as np
>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(2)
>>> np.allclose(gc.adjacency_graph_energy(G), 2.0)
True

graphcalc.graphs.invariants.spectral.adjacency_inertia_triple(G: Graph, tol: float = 1e-10) → AdjacencyInertia

Compute the inertia triple of the adjacency matrix of a graph.

For a graph \(G\), the adjacency inertia triple is

\[(p(G), n(G), z(G)),\]

where \(p(G)\), \(n(G)\), and \(z(G)\) denote the numbers of positive, negative, and zero eigenvalues of \(A(G)\), respectively.

Since the adjacency matrix of an undirected graph is real symmetric, these quantities satisfy

\[p(G) + n(G) + z(G) = |V(G)|.\]

Parameters:

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

• tol (float, optional) – Numerical tolerance used to classify eigenvalues as positive, negative, or zero. Default is 1e-10.

Returns:

The adjacency inertia triple of \(G\).

Return type:

AdjacencyInertia

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(3)
>>> gc.adjacency_inertia_triple(G)
AdjacencyInertia(positive=1, negative=1, zero=1)

graphcalc.graphs.invariants.spectral.adjacency_matrix(G: Graph) → ndarray

Compute the adjacency matrix of a graph.

For a simple graph \(G = (V,E)\) with vertex set \(V = \{0,1,\dots,n-1\}\), the adjacency matrix \(A(G)\) is the \(n \times n\) matrix defined by:

\[\begin{split}A_{ij} = \begin{cases} 1 & \text{if } \{i,j\} \in E, \\ 0 & \text{otherwise}. \end{cases}\end{split}\]

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph. Vertex labels will be relabeled to consecutive integers \(0,1,\dots,n-1\) for the matrix representation.

Returns:

The adjacency matrix \(A(G)\) as a dense NumPy array.

Return type:

numpy.ndarray

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> gc.adjacency_matrix(G)
array([[0, 1, 1, 0],
       [1, 0, 0, 1],
       [1, 0, 0, 1],
       [0, 1, 1, 0]])

graphcalc.graphs.invariants.spectral.adjacency_negative_inertia_index(G: Graph, tol: float = 1e-10) → int

Compute the negative inertia index of the adjacency matrix of a graph.

For a graph \(G\) with adjacency eigenvalues \(\lambda_1,\dots,\lambda_n\), the negative inertia index is

\[n(G) = |\{i : \lambda_i < 0\}|.\]

Numerically, eigenvalues less than -tol are counted as negative.

Parameters:

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

• tol (float, optional) – Numerical tolerance used to decide negativity. Eigenvalues less than -tol are counted as negative. Default is 1e-10.

Returns:

The number of negative adjacency eigenvalues of \(G\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(3)
>>> gc.adjacency_negative_inertia_index(G)
1

graphcalc.graphs.invariants.spectral.adjacency_nullity(G: Graph, tol: float = 1e-10) → int

Compute the adjacency nullity of a graph.

For a graph \(G\) with adjacency matrix \(A(G)\), the adjacency nullity is the multiplicity of the eigenvalue \(0\) in the spectrum of \(A(G)\). Equivalently,

\[\eta(G) = \dim(\ker(A(G))).\]

Numerically, eigenvalues whose absolute value is at most tol are treated as zero.

Parameters:

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

• tol (float, optional) – Numerical tolerance used to decide whether an eigenvalue is zero. Default is 1e-10.

Returns:

The adjacency nullity of \(G\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(3)
>>> gc.adjacency_nullity(G)
1

graphcalc.graphs.invariants.spectral.adjacency_positive_inertia_index(G: Graph, tol: float = 1e-10) → int

Compute the positive inertia index of the adjacency matrix of a graph.

For a graph \(G\) with adjacency eigenvalues \(\lambda_1,\dots,\lambda_n\), the positive inertia index is

\[p(G) = |\{i : \lambda_i > 0\}|.\]

Numerically, eigenvalues greater than tol are counted as positive.

Parameters:

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

• tol (float, optional) – Numerical tolerance used to decide positivity. Eigenvalues greater than tol are counted as positive. Default is 1e-10.

Returns:

The number of positive adjacency eigenvalues of \(G\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(3)
>>> gc.adjacency_positive_inertia_index(G)
1

graphcalc.graphs.invariants.spectral.adjacency_rank(G: Graph, tol: float = 1e-10) → int

Compute the rank of the adjacency matrix of a graph.

For a graph \(G\) with adjacency matrix \(A(G)\), the adjacency rank is

\[\operatorname{rank}(A(G)).\]

In terms of the adjacency inertia indices, one has

\[\operatorname{rank}(A(G)) = p(G) + n(G),\]

since zero eigenvalues do not contribute to the rank.

Parameters:

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

• tol (float, optional) – Numerical tolerance used when classifying eigenvalues. Default is 1e-10.

Returns:

The rank of \(A(G)\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(3)
>>> gc.adjacency_rank(G)
2

graphcalc.graphs.invariants.spectral.adjacency_signature(G: Graph, tol: float = 1e-10) → int

Compute the signature of the adjacency matrix of a graph.

For a graph \(G\), the adjacency signature is defined by

\[s(G) = p(G) - n(G),\]

where \(p(G)\) and \(n(G)\) are the positive and negative inertia indices of \(A(G)\).

Parameters:

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

• tol (float, optional) – Numerical tolerance used when classifying eigenvalues. Default is 1e-10.

Returns:

The adjacency signature of \(G\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> gc.adjacency_signature(G)
0

graphcalc.graphs.invariants.spectral.adjacency_smallest_positive_eigenvalue(G: Graph, tol: float = 1e-12) → float | None

Compute the smallest strictly positive adjacency eigenvalue of a graph.

If the adjacency spectrum of \(G\) is

\[\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n,\]

then this function returns the smallest eigenvalue satisfying \(\lambda_i > 0\).

Numerically, eigenvalues greater than tol are treated as positive. If no such eigenvalue exists, the function returns None.

Parameters:

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

• tol (float, optional) – Numerical tolerance used to test positivity. Default is 1e-12.

Returns:

The smallest strictly positive adjacency eigenvalue of \(G\), or None if the adjacency matrix has no positive eigenvalues.

Return type:

float or None

Examples

>>> import numpy as np
>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(3)
>>> np.allclose(gc.adjacency_smallest_positive_eigenvalue(G), np.sqrt(2))
True

graphcalc.graphs.invariants.spectral.adjacency_zero_inertia_index(G: Graph, tol: float = 1e-10) → int

Compute the zero inertia index of the adjacency matrix of a graph.

The zero inertia index is the number of zero adjacency eigenvalues. For an undirected graph, this is exactly the adjacency nullity:

\[z(G) = \eta(G).\]

Numerically, eigenvalues whose absolute value is at most tol are treated as zero.

Parameters:

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

• tol (float, optional) – Numerical tolerance used to decide whether an eigenvalue is zero. Default is 1e-10.

Returns:

The zero inertia index of \(G\).

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(3)
>>> gc.adjacency_zero_inertia_index(G)
1

graphcalc.graphs.invariants.spectral.algebraic_connectivity(G: Graph) → float

Compute the algebraic connectivity of a graph.

For a graph \(G = (V,E)\) with Laplacian matrix \(L(G)\), the algebraic connectivity is defined as the second-smallest Laplacian eigenvalue:

\[a(G) = \lambda_2(L(G)),\]

where the eigenvalues are ordered

\[0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n.\]

Properties

• \(a(G) > 0\) if and only if \(G\) is connected.

• Larger values of \(a(G)\) indicate greater graph connectivity and expansion.

• The corresponding eigenvector is known as the Fiedler vector, used in spectral clustering and partitioning.

param G:

The input graph.

type G:

networkx.Graph or graphcalc.SimpleGraph

returns:

The algebraic connectivity \(a(G)\) of the graph.

rtype:

float

Examples

>>> import numpy as np
>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> np.allclose(gc.algebraic_connectivity(G), 2.0)
True

graphcalc.graphs.invariants.spectral.laplacian_eigenvalues(G: Graph)

Compute the eigenvalues of the (combinatorial) Laplacian matrix of a graph.

For a graph \(G=(V,E)\), the (combinatorial) Laplacian is

\[L(G) \;=\; D(G) - A(G),\]

where \(A(G)\) is the adjacency matrix and \(D(G)\) is the diagonal matrix of vertex degrees. The Laplacian eigenvalues are the eigenvalues of \(L(G)\), equivalently the values \(\lambda\) satisfying

\[\det(\lambda I - L(G)) = 0.\]

Laplacian eigenvalues are real and nonnegative and play a central role in spectral graph theory. In particular:

• The multiplicity of 0 equals the number of connected components of \(G\).

• The second-smallest eigenvalue is the algebraic connectivity.

• The largest eigenvalue provides bounds for various graph invariants.

Parameters:

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

Returns:

The Laplacian eigenvalues of \(L(G)\), sorted in nondecreasing order.

Return type:

numpy.ndarray

Examples

>>> import numpy as np
>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> np.allclose(gc.laplacian_eigenvalues(G), np.array([0., 2., 2., 4.]))
True

The number of zero eigenvalues equals the number of connected components:

>>> import numpy as np
>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> H = nx.disjoint_union(nx.path_graph(3), nx.path_graph(2))  # 2 components
>>> eigs = gc.laplacian_eigenvalues(H)
>>> int(np.sum(np.isclose(eigs, 0.0)))
2

graphcalc.graphs.invariants.spectral.laplacian_matrix(G: Graph) → array

Compute the Laplacian matrix of a graph.

For a graph \(G = (V,E)\) with adjacency matrix \(A(G)\) and degree matrix \(D(G) = \mathrm{diag}(\deg(v_0), \dots, \deg(v_{n-1}))\), the combinatorial Laplacian matrix is defined as:

\[L(G) = D(G) - A(G).\]

This symmetric positive semidefinite matrix encodes important structural properties of the graph, including connectivity, spanning trees, and spectral invariants.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph. Vertex labels will be relabeled to consecutive integers \(0,1,\dots,n-1\) for the matrix representation.

Returns:

The Laplacian matrix \(L(G)\) as a dense NumPy array.

Return type:

numpy.ndarray

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> gc.laplacian_matrix(G)
array([[ 2, -1, -1,  0],
       [-1,  2,  0, -1],
       [-1,  0,  2, -1],
       [ 0, -1, -1,  2]])

graphcalc.graphs.invariants.spectral.largest_laplacian_eigenvalue(G: Graph) → float64

Compute the largest Laplacian eigenvalue of a graph.

For a graph \(G = (V,E)\) with Laplacian matrix \(L(G)\), the largest Laplacian eigenvalue is

\[\lambda_{\max}(G) = \max_i \lambda_i(L(G)),\]

where \(0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n\) are the eigenvalues of \(L(G)\).

Properties

• Always satisfies \(\lambda_{\max}(G) \leq 2\Delta(G)\), where \(\Delta(G)\) is the maximum degree.

• Provides information about expansion, connectivity, and can be used in spectral partitioning.

• Together with the algebraic connectivity (second-smallest Laplacian eigenvalue), it bounds the Laplacian spectrum.

param G:

The input graph.

type G:

networkx.Graph or graphcalc.SimpleGraph

returns:

The largest Laplacian eigenvalue \(\lambda_{\max}(G)\).

rtype:

float

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> np.allclose(gc.largest_laplacian_eigenvalue(G), 4.0)
True

graphcalc.graphs.invariants.spectral.second_largest_adjacency_eigenvalue(G: Graph) → float64

Compute the second largest eigenvalue of the adjacency matrix.

For a graph \(G=(V,E)\) with adjacency matrix \(A(G)\), let the eigenvalues of \(A(G)\) be ordered as

\[\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_{|V|}.\]

This function returns \(\lambda_{|V|-1}\), the second largest eigenvalue of \(A(G)\).

Notes

• The second largest adjacency eigenvalue is important in the study of graph expansion, mixing rates of random walks, and spectral gaps.

• For a d-regular graph, the gap \(d - \lambda_{|V|-1}\) measures how well-connected (expander-like) the graph is.

Parameters:

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

Returns:

The second largest eigenvalue of the adjacency matrix.

Return type:

float

Examples

>>> import numpy as np
>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> np.allclose(gc.second_largest_adjacency_eigenvalue(G), 0.0)
True

graphcalc.graphs.invariants.spectral.smallest_adjacency_eigenvalue(G: Graph) → float64

Compute the smallest eigenvalue of the adjacency matrix.

For a graph \(G=(V,E)\) with adjacency matrix \(A(G)\), let the eigenvalues of \(A(G)\) be ordered as

\[\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_{|V|}.\]

This function returns \(\lambda_1\), the smallest adjacency eigenvalue of \(G\).

Notes

• The smallest adjacency eigenvalue is often negative unless the graph is complete multipartite.

• It appears in Hoffman’s bound for the chromatic number:

  \[\chi(G) \geq 1 - \frac{\lambda_{\max}}{\lambda_{\min}},\]

  where \(\lambda_{\max}\) is the largest adjacency eigenvalue and \(\lambda_{\min}\) is the smallest.

• Also useful in spectral extremal graph theory and characterizations of special graph classes (e.g., line graphs).

Parameters:

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

Returns:

The smallest eigenvalue of the adjacency matrix.

Return type:

float

Examples

>>> import numpy as np
>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> np.allclose(gc.smallest_adjacency_eigenvalue(G), -2.0)
True

graphcalc.graphs.invariants.spectral.spectral_radius(G: Graph) → float

Compute the spectral radius of a graph.

For a graph \(G = (V,E)\) with adjacency matrix \(A(G)\), the spectral radius is the largest eigenvalue in absolute value:

\[\rho(G) = \max_i |\lambda_i(A(G))|.\]

Properties

• For nonnegative, symmetric adjacency matrices (as in simple graphs), the spectral radius equals the largest eigenvalue \(\lambda_{\max}\).

• \(\rho(G)\) provides bounds on many invariants, such as maximum degree and average degree:

  \[\bar{d}(G) \leq \rho(G) \leq \Delta(G).\]

• The eigenvector associated with \(\rho(G)\) is nonnegative by the Perron–Frobenius theorem and often called the Perron vector.

param G:

The input graph.

type G:

networkx.Graph or graphcalc.SimpleGraph

returns:

The spectral radius \(\rho(G)\) of the adjacency matrix.

rtype:

float

Examples

>>> import numpy as np
>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> np.allclose(gc.spectral_radius(G), 2.0)
True

graphcalc.graphs.invariants.spectral.zero_adjacency_eigenvalues_count(G: Graph) → int

Count the number of zero eigenvalues of the adjacency matrix.

For a graph \(G=(V,E)\) with adjacency matrix \(A(G)\), this function returns the multiplicity of the eigenvalue \(0\) in the spectrum of \(A(G)\):

\[m_0(G) \;=\; \bigl|\{\, i : \lambda_i(A(G)) = 0 \,\}\bigr|.\]

Properties

• \(m_0(G)\) is the nullity of the adjacency matrix \(A(G)\).

• It is related to rank by \(\mathrm{rank}(A(G)) = |V(G)| - m_0(G)\).

• In many families of graphs, the nullity reflects structural redundancy.

param G:

The input graph.

type G:

networkx.Graph or graphcalc.SimpleGraph

returns:

The multiplicity of the zero eigenvalue of \(A(G)\).

rtype:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)
>>> gc.zero_adjacency_eigenvalues_count(G)
2