Glossary

Key concepts and terminology used throughout SMOL.

QUICK JUMP
A B C D E F G H I K L N P R S T V W

G

graph6
A compact ASCII encoding for simple undirected graphs. Each graph6 string uniquely represents a graph (up to isomorphism). The format encodes the upper triangle of the adjacency matrix.

Example: D?{ represents the star graph $K_{1,4}$ (4 leaves connected to a center).

Read the full specification →

A

Adjacency matrix
The $n \times n$ matrix $A$ where $A_{ij} = 1$ if vertices $i$ and $j$ are connected, 0 otherwise. Symmetric for undirected graphs. Eigenvalues are real.

K

Kirchhoff Laplacian (Combinatorial Laplacian)
$L = D - A$, where $D$ is the diagonal degree matrix and $A$ is the adjacency matrix. Also called the combinatorial or standard Laplacian. Eigenvalues are real and non-negative: $0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n \leq 2\Delta$, where $\Delta$ is the maximum degree. The second-smallest eigenvalue $\lambda_2$ is the algebraic connectivity (Fiedler value).

S

Signless Laplacian
$Q = D + A$, where $D$ is the diagonal degree matrix and $A$ is the adjacency matrix. The "positive" counterpart to the Kirchhoff Laplacian. All eigenvalues are real and non-negative. Related to chromatic number and bipartiteness detection.

L

Normalized Laplacian
The symmetric normalized Laplacian: $L = I - D^{-1/2} A D^{-1/2}$, where $D$ is the diagonal degree matrix. Eigenvalues are real and lie in $[0, 2]$. Has the same eigenvalues as the random walk Laplacian $I - D^{-1} A$.

N

Non-backtracking matrix (Hashimoto)
A $2m \times 2m$ matrix indexed by directed edges. $B_{e \to f} = 1$ if edge $e$ leads into edge $f$ without backtracking (the target of $e$ equals the source of $f$, and $f$ is not the reverse of $e$). Eigenvalues are generally complex.
Non-backtracking Laplacian
$L_B = I - D^{-1} B$, where $B$ is the non-backtracking matrix and $D$ is the diagonal matrix of out-degrees in the directed edge graph. Represents a random walk on directed edges. Eigenvalues are generally complex.

D

Distance matrix
The $n \times n$ matrix $D$ where $D_{ij}$ is the shortest path length between vertices $i$ and $j$. Only defined for connected graphs. Eigenvalues are real. The distance spectrum captures structural information about graph diameter and centrality.
Spectrum
The multiset of eigenvalues of a matrix. Two graphs are cospectral if they have the same spectrum for a given matrix type.
Cospectral (isospectral)
Two non-isomorphic graphs that share the same spectrum for a particular matrix type. Cospectral graphs are indistinguishable by spectral methods using that matrix alone.
Spectral hash
A 16-character hash of the sorted eigenvalues, used for fast cospectral lookup. Two graphs with the same hash have the same spectrum (within numerical precision).
Spectral distance
A measure of dissimilarity between two spectra, computed using the Earth Mover's Distance (Wasserstein metric). For real eigenvalues (adjacency, Kirchhoff, signless, normalized Laplacian), this is the 1D Wasserstein distance between sorted eigenvalue sequences. For complex eigenvalues (NB, NBL matrices), this is the 2D Wasserstein distance treating eigenvalues as points $(λ_r, λ_i)$ in the complex plane. A distance of 0 indicates cospectral graphs; smaller distances indicate more similar spectra.
GM switching (Godsil-McKay)
A graph operation that preserves the adjacency spectrum using an equitable partition and a switching set. Given a graph $G$ with an equitable partition $V = D \cup C_1 \cup \cdots \cup C_k$, where $D$ is a switching set, GM switching produces a cospectral mate $H$ by changing which vertices in $D$ connect to which vertices in each partition class.

Requirements:
  • The partition must be equitable: all vertices in the same class have the same number of neighbors in each other class
  • Each vertex in the switching set $D$ must connect to all, none, or exactly half of each partition class $C_i$
  • The switching operation swaps which half of each class the vertex connects to
GM switching is one of the most common explanations for adjacency cospectrality, covering approximately 43% of adjacency-cospectral graphs at $n=9$.

Reference: Godsil and McKay (1982), "Constructing cospectral graphs"
Switching mechanism
A systematic graph operation that preserves the spectrum for some matrix type. Known mechanisms include GM switching (adjacency), Seidel switching (adjacency), and various edge-switching operations. Understanding which mechanisms explain observed cospectrality is an active area of research.

E

Equitable partition
A partition of vertices $V = C_1 \cup C_2 \cup \cdots \cup C_k$ where all vertices in the same class $C_i$ have the same number of neighbors in each class $C_j$ (including $C_i$ itself). Equitable partitions are central to GM switching and other spectral graph theory results.

B

Bipartite
A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other. Equivalently, a graph with no odd cycles.

P

Planar
A graph that can be drawn in the plane without any edges crossing.

R

Regular
A graph where every vertex has the same degree.
Diameter
The maximum shortest path distance between any two vertices. Only defined for connected graphs.
Girth
The length of the shortest cycle in the graph. Undefined ($\infty$) for acyclic graphs (trees/forests).
Radius
The minimum eccentricity of any vertex, where eccentricity is the maximum distance from that vertex to any other vertex.

C

Clique number
The size of the largest clique (complete subgraph) in the graph.
Chromatic number
The minimum number of colors needed to color the vertices such that no two adjacent vertices share the same color. SMOL stores a greedy upper bound.
Degree
The number of edges incident to a vertex. SMOL stores the minimum and maximum degree in the graph, shown as a range [min, max].

T

Triangle count
The number of triangles (3-cycles) in the graph. A triangle is a set of three vertices that are mutually adjacent.

Network Science Properties

Algebraic connectivity
The second-smallest eigenvalue of the Laplacian matrix (also called the Fiedler value). A connected graph has algebraic connectivity $> 0$. Larger values indicate stronger connectivity.
Global clustering (transitivity)
The ratio of closed triangles to connected triples in the graph: $C = \frac{3 \times \text{triangles}}{\text{connected triples}}$. Measures the overall tendency of nodes to cluster together.
Average local clustering
The average of local clustering coefficients across all nodes. Each node's local clustering coefficient is the fraction of possible triangles through that node that exist.
Average path length
The mean shortest path distance between all pairs of vertices. Only defined for connected graphs.
Degree assortativity
Pearson correlation coefficient of degree between connected node pairs. Positive values mean high-degree nodes tend to connect to high-degree nodes; negative values indicate high-degree nodes connect to low-degree nodes.
Complete graph ($K_n$)
A graph where every pair of vertices is connected by an edge. Has $\binom{n}{2} = n(n-1)/2$ edges.
Cycle ($C_n$)
A connected 2-regular graph. The vertices form a single closed loop.
Path ($P_n$)
A tree where every vertex has degree at most 2. The simplest connected graph structure.
Star ($K_{1,n-1}$)
A tree with one central vertex connected to all others. The center has degree $n-1$, all other vertices have degree 1.

W

Wheel ($W_n$)
A cycle with an additional central vertex (hub) connected to all cycle vertices. The hub has degree $n-1$, rim vertices have degree 3.
Complete bipartite ($K_{a,b}$)
A bipartite graph where every vertex in one part is connected to every vertex in the other. Has $a \cdot b$ edges.
Complete multipartite ($K_{n_1, n_2, \ldots}$)
A graph whose vertices are partitioned into groups, with edges between all pairs of vertices in different groups and no edges within groups. Generalizes complete bipartite graphs.
Tree
A connected acyclic graph. Equivalently, a connected graph with $n-1$ edges.
Prism ($C_n \square K_2$)
The Cartesian product of a cycle and an edge. Two parallel cycles connected by matching edges. Also called a circular ladder.
Ladder ($P_n \square K_2$)
The Cartesian product of a path and an edge. Two parallel paths connected by rungs.
Windmill ($Wd(k, n)$)
A graph of $n$ copies of $K_k$ sharing a single universal vertex. The friendship graph $F_n$ is the special case $Wd(3, n)$ (triangles sharing a vertex).

F

Fan ($F_{1,n}$)
A path $P_n$ with an additional vertex connected to all path vertices. Similar to a wheel but with a path instead of a cycle.
Petersen graph
The famous 10-vertex, 15-edge graph. 3-regular with girth 5 and diameter 2. A counterexample to many graph theory conjectures.
Cubic (3-regular)
A graph where every vertex has degree exactly 3. An important class in spectral graph theory.
Triangle-free
A graph containing no triangles (3-cycles). Equivalently, has girth $\geq 4$ or clique number 2.
Line graph
A graph $L(G)$ whose vertices represent the edges of $G$, with two vertices adjacent if the corresponding edges share an endpoint. Characterized by forbidden induced subgraphs.
Strongly regular
A regular graph where every pair of adjacent vertices has the same number of common neighbors, and every pair of non-adjacent vertices also has the same number of common neighbors. Parameters denoted $srg(n, k, \lambda, \mu)$.

V

Vertex-transitive
A graph whose automorphism group acts transitively on vertices—every vertex can be mapped to any other by some symmetry. All vertex-transitive graphs are regular.
Eulerian
A connected graph where every vertex has even degree. Such graphs have a closed walk that visits every edge exactly once (an Eulerian circuit).

References

For more details on spectral graph theory and switching mechanisms: