Fact-checked by Grok 2 weeks ago

Algebraic graph theory

Algebraic graph theory is a branch of mathematics that applies algebraic techniques, particularly linear algebra and spectral methods, to investigate the combinatorial properties of graphs, such as connectivity, coloring, and expansion.^[1] It primarily involves associating algebraic structures like matrices with graphs to reveal insights into their structural features through eigenvalues and eigenvectors.^[2] Central to the field are key algebraic objects derived from graphs, including the adjacency matrix A, an n \times n symmetric matrix where A_{ij} = 1 if vertices i and j are adjacent and 0 otherwise, and the Laplacian matrix L = D - A, where D is the diagonal degree matrix.^[1] The spectrum of a graph refers to the multiset of eigenvalues of A or L, which encode properties like the graph's diameter, chromatic number, and bipartiteness; for instance, bipartite graphs have spectra symmetric about zero.^[3] The second-smallest eigenvalue of L, known as the Fiedler value \lambda_2, quantifies algebraic connectivity, with \lambda_2 > 0 if and only if the graph is connected.^[1] Notable results include bounds on the chromatic number \chi(G) \leq 1 + \lambda_{\max}(A), where \lambda_{\max} is the largest eigenvalue of the adjacency matrix, and applications to random walks via the normalized Laplacian N = D^{-1/2} L D^{-1/2}, which models convergence to stationary distributions.^[3] Algebraic graph theory also employs group theory for automorphism groups and equitable partitions, which refine the spectrum to study symmetries and quotients of graphs.^[2] The field has roots in early 20th-century work, such as Perron-Frobenius theory applied to nonnegative matrices (Perron 1907; Frobenius 1912), and gained momentum through contributions like Fiedler's 1973 introduction of algebraic connectivity.^[1] Modern applications span network analysis, error-correcting codes, spectral graph drawing—using low-frequency eigenvectors for visualization—and expander graphs, where small spectral gaps enable efficient algorithms for partitioning and linear system solving.^[1] Theorems like the Matrix-Tree Theorem, counting spanning trees via the Laplacian determinant, underscore its combinatorial power.^[2]

Fundamentals

Definitions and Scope

Algebraic graph theory is a branch of mathematics that applies algebraic techniques, including linear algebra and group theory, to investigate the combinatorial properties of graphs—structures comprising a set of vertices connected by edges representing incidences between them. This field translates graph-theoretic problems into algebraic frameworks, enabling the use of tools like matrices and symmetries to derive insights into graph structure and behavior. Unlike traditional graph theory, which may rely on direct enumeration or geometric visualization, algebraic graph theory leverages these methods to uncover invariants and homomorphisms that capture essential properties of graphs.^[4]^[5]^[6] The scope of algebraic graph theory primarily encompasses finite undirected simple graphs, though it extends to directed graphs, where edges have orientation, and weighted graphs, where edges carry numerical values. It distinguishes itself from geometric graph theory, which focuses on embeddings in space and planarity; combinatorial graph theory, centered on counting substructures like paths or cycles; and algorithmic graph theory, which emphasizes computational tractability and optimization. Key emphases include the development of algebraic invariants, such as spectra and polynomials, and the study of homomorphisms between graphs, providing a deeper understanding of symmetry and connectivity beyond purely structural descriptions.^[5]^[6]^[4] Prerequisite concepts in graph theory include simple graphs, defined as structures with a nonempty vertex set V and an edge set E consisting of unordered pairs from V, without loops (edges from a vertex to itself) or multiple edges between the same pair of vertices, and multigraphs, which permit multiple edges between vertices but exclude loops. On the algebraic side, foundational elements are vector spaces, nonempty sets V equipped with addition and scalar multiplication over a field (satisfying closure, associativity, commutativity, identity, inverses, and distributivity), and groups, sets G with a binary operation satisfying closure, associativity, identity, and inverses. These basics enable the formulation of graph properties in algebraic terms without requiring advanced derivations.^[7]^[8]^[9]^[10]

Historical Development

The roots of algebraic graph theory trace back to the mid-19th century, when early applications of linear algebra to graph-like structures emerged in the context of electrical networks and combinatorial problems. In 1847, Gustav Kirchhoff introduced the use of determinants of submatrices of the Laplacian matrix to count the number of spanning trees in a graph, originally motivated by solving systems of equations for galvanic currents in linear circuits; this result, now known as the Matrix-Tree Theorem, marked one of the first algebraic tools for enumerating graph structures.^[11] Toward the end of the century, graph coloring problems gained attention, with Alfred Bray Kempe's 1879 attempt to prove the four-color theorem using recursive color swaps on planar maps highlighting the interplay between algebraic invariants and graph embeddings, though his proof contained a subtle flaw later exposed in 1890.^[12] These works laid foundational connections between matrices, polynomials, and graph properties, predating the formal unification of the field. The late 19th and early 20th centuries saw the integration of group theory into graph studies, beginning with Arthur Cayley's 1878 proposal of graphical representations for abstract groups, where edges correspond to group generators, introducing Cayley graphs as a bridge between algebraic structures and combinatorial objects.^[13] Spectral methods began to crystallize in the 1930s through Erich Hückel's quantum mechanical model for π-electron energies in organic molecules, which relied on eigenvalues of the adjacency matrix to approximate molecular stability. This approach was extended in the 1970s by B. J. McClelland, who developed graphical factorization techniques for solving Hückel secular equations, enabling efficient computation of graph spectra for symmetric molecular graphs and foreshadowing broader applications in chemistry.^[14] Key milestones in group-theoretic graph theory included Robert Frucht's series of results from 1939 to 1949, culminating in his 1949 theorem that every finite abstract group can be realized as the automorphism group of some finite graph, achieved through constructions of graphs with prescribed symmetries. Influential mathematicians shaped the field's maturation, with Arthur Cayley pioneering group-graph correspondences, László Babai advancing algorithmic applications of automorphism groups to the graph isomorphism problem starting in the late 1970s, and Norman Biggs synthesizing classical and modern algebraic techniques in his 1993 textbook, which emphasized linear algebra and group actions for graph enumeration and symmetry analysis. The 1960s and 1970s saw further development in spectral methods, including works by Dragoslav Cvetković, Peter Rowlinson, and others on graph spectra, as well as Miroslav Fiedler's 1973 introduction of algebraic connectivity using the Laplacian spectrum. Post-1970s developments accelerated with the rise of computational tools, enabling numerical studies of large graph spectra and automorphism computations, as algebraic methods interfaced with emerging software for matrix diagonalization and group enumeration. In recent years, as of 2025, integrations have expanded into quantum computing, where algebraic graph invariants inform quantum walks and error-correcting codes on graphs, and network science, leveraging spectral decompositions for community detection in complex systems.^[15] Additionally, algebraic frameworks underpin machine learning on graphs, particularly in spectral graph neural networks that embed group symmetries for tasks like node classification in heterogeneous networks.^[16] Early coloring motivations, such as those in Kempe's work, later inspired the chromatic polynomial as an algebraic invariant for counting proper colorings.

Core Algebraic Tools

Graph Matrices

In algebraic graph theory, the adjacency matrix serves as a fundamental linear algebraic representation of a graph. For a graph G with vertex set V = \{v_1, \dots, v_n\}, the adjacency matrix A(G) is the n \times n matrix where the entry A_{ij} equals the number of edges joining vertices v_i and v_j, with each loop at v_i counted twice if i = j.^[17] For undirected simple graphs without loops or multiple edges, A(G) is a symmetric 0-1 matrix with zeros on the diagonal and A_{ij} = 1 if there is an edge between v_i and v_j, and 0 otherwise.^[18] A key property of the adjacency matrix is that its powers encode information about walks in the graph: the (i,j)-entry of A^k counts the number of walks of length k from v_i to v_j.^[19] The trace of A, denoted \operatorname{tr}(A), equals twice the number of loops in the graph under the convention where loops contribute twice to the diagonal entries.^[17] Additionally, the row sums of A correspond to the degrees of the vertices, providing a direct link to graph degrees via linear algebra.^[19] The incidence matrix offers another essential matrix representation, particularly useful for oriented graphs and incidence structures. For a graph G with n vertices and m edges, the incidence matrix B(G) is an n \times m matrix with rows indexed by vertices and columns by edges; for a directed edge from v_i to v_j, the entries are B_{i,e} = -1, B_{j,e} = 1, and 0 elsewhere, while undirected graphs use absolute values or arbitrary orientations.^[20] This matrix captures vertex-edge incidences and is instrumental in defining cut spaces over fields like \mathbb{R} or \mathbb{F}_2, where the column space relates to cycle and cut subspaces in the graph.^[21] Basic properties of these matrices include the symmetry of A for undirected graphs, ensuring real eigenvalues, and the fact that A^2 has diagonal entries equal to the degrees of vertices in simple graphs without loops.^[19] The eigenvalues of A are connected to vertex degrees, with the largest eigenvalue bounded by the maximum degree, though detailed spectral interpretations are deferred to later analysis.^[22] As an illustrative example, consider the complete graph K_3 on three vertices with no loops. Its adjacency matrix is

A(K_3) = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}.

The matrix A^2(K_3) counts walks of length 2, yielding

A^2(K_3) = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix},

where the diagonal entries are the degrees (each vertex has degree 2), and off-diagonal entries indicate one walk of length 2 between any pair of distinct vertices.^[19] The trace of A(K_3) is 0, consistent with the absence of loops.^[18] These graph matrices form the foundational tools for algebraic manipulations in graph theory, enabling the application of linear algebra techniques such as matrix multiplication and eigenvalue computations to derive graph invariants and structural properties.

Automorphism Groups

The automorphism group of a graph G, denoted \Aut(G), is the set of all bijections \phi: V(G) \to V(G) that preserve adjacency, meaning uv \in E(G) if and only if \phi(u)\phi(v) \in E(G), forming a group under composition. The order |\Aut(G)| provides a measure of the graph's symmetry, as larger groups indicate more permutations that leave the structure unchanged.^[23] A fundamental property is observed in vertex-transitive graphs, where \Aut(G) acts transitively on the vertex set, allowing any vertex to be mapped to any other while preserving the graph's edges. Frucht's theorem establishes that every finite group is isomorphic to \Aut(G) for some finite graph G; moreover, in 1949, Frucht extended this to show that such a realization is possible with a connected 3-regular (cubic) graph.^[24] This result highlights the flexibility of graph symmetries in encoding arbitrary finite group structures. Illustrative examples include the cycle graph C_n for n \geq 3, whose \Aut(C_n) is the dihedral group D_n of order $2n, generated by rotations and reflections. The Petersen graph provides another case, with |\Aut| = 120 and \Aut isomorphic to the symmetric group S_5.^[25] Computing \Aut(G) for small graphs often employs the Schreier–Sims algorithm, which constructs a base and strong generating set to determine the group's structure and order efficiently.^[26] Broader connections to geometric group theory emerge through analyzing these groups as actions on graphs viewed as metric spaces, revealing symmetries via combinatorial and topological invariants. For infinite graphs, automorphism groups frequently link to Cayley graphs, offering symmetric realizations of infinite groups through regular actions on vertices.^[27]

Spectral Methods

Adjacency Matrix and Eigenvalues

The spectrum of the adjacency matrix A of a graph G with n vertices is the multiset of its eigenvalues \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n, where each \lambda_i is real since A is symmetric.^[28] The multiplicity of an eigenvalue refers to the number of times it appears in this ordered list, which provides insights into the graph's symmetry and structure. In connected graphs, the spectral gap \lambda_1 - \lambda_2 serves as a measure of expansion properties, analogous to algebraic connectivity in related spectral contexts.^[29] A fundamental result is the Perron-Frobenius theorem applied to the adjacency matrix of a connected graph, which states that the largest eigenvalue \lambda_1 is simple (multiplicity 1), positive, and has a positive eigenvector, while all other eigenvalues satisfy |\lambda_i| \leq \lambda_1 for i \geq 2, with equality possible in the bipartite case.^[30] This theorem implies that \lambda_1 equals the average degree in regular graphs and bounds the graph's connectivity.^[31] The Hoffman-Singleton theorem (1960) classifies Moore graphs of diameter 2, showing that such graphs exist only for degrees 2, 3, 7, or possibly 57, and derives tight spectral constraints: for a d-regular Moore graph of diameter 2 on n = 1 + d + d(d-1) vertices, the adjacency spectrum consists of \lambda_1 = d (multiplicity 1), \theta = \frac{-1 + \sqrt{4d - 3}}{2} (with integer multiplicity), and \tau = \frac{-1 - \sqrt{4d - 3}}{2} (with integer multiplicity n-1 minus the multiplicity of \theta).^[32] This result uses the eigenvalues to prove non-existence for most degrees, with the Hoffman-Singleton graph achieving the bound for d=7.^[33] A representative example is the Petersen graph, a 3-regular graph on 10 vertices with adjacency spectrum $3^1 1^5 (-2)^4.^[34] Here, the largest eigenvalue $3 matches the degree, the multiplicity of $1 reflects intermediate connectivity, and -2 (with multiplicity 4) indicates strong regularity.^[28] Spectral properties yield bounds on graph parameters, such as Hoffman's ratio bound for the independence number \alpha(G) of a k-regular graph: \alpha(G) \leq n \frac{|\lambda_n|}{k - \lambda_n}, or equivalently \alpha(G) \leq n \left(1 - \frac{k}{k - \lambda_n}\right) when \lambda_n < 0.^[35] This bound is tight for strongly regular graphs like the Petersen graph, where \alpha(G) = 4 matches the estimate using \lambda_n = -2.^[28] The eigenvalues also count walks via spectral decomposition: the number of closed walks of length k in G is \sum_{i=1}^n \lambda_i^k = \operatorname{tr}(A^k).^[36] For instance, in the Petersen graph, the number of closed walks of length 3 is $3^3 + 5 \cdot 1^3 + 4 \cdot (-2)^3 = 27 + 5 - 32 = 0, confirming the absence of triangles.^[34]

Laplacian Matrix and Applications

The Laplacian matrix L of a graph G with n vertices is defined as L = D - A, where D is the diagonal degree matrix with D_{ii} equal to the degree of vertex i, and A is the adjacency matrix of G.^[37] This construction relates the Laplacian to the adjacency matrix via L = D - A, highlighting its role in capturing degree-adjusted connectivity.^[37] A key property of the Laplacian is its quadratic form: for any vector x \in \mathbb{R}^n, x^T L x = \sum_{\{i,j\} \in E} (x_i - x_j)^2, which measures the total squared differences across edges and underscores L's positive semidefiniteness.^[37] The spectrum of L consists of real, nonnegative eigenvalues $0 = \mu_1 \leq \mu_2 \leq \cdots \leq \mu_n, with \mu_1 = 0 corresponding to the all-ones eigenvector, and the multiplicity of zero equal to the number of connected components.^[37] For a connected graph, \mu_2 > 0, known as the algebraic connectivity, which quantifies the graph's connectivity: larger \mu_2 indicates stronger overall connectivity, while \mu_2 \to 0 signals near-disconnectivity.^[38] The Fiedler vector, the eigenvector corresponding to \mu_2, provides a natural partitioning of the graph by signing its components: vertices with positive and negative entries form two sets that minimize edge cuts relative to size, aiding in spectral graph partitioning.^[38] Cheeger's inequality further links \mu_2 to edge expansion, stating that for the normalized Laplacian, the spectral gap satisfies $2h_G \geq \lambda_G \geq h_G^2 / 2, where h_G is the Cheeger constant measuring the minimum edge boundary over subsets of volume at most half the total.^[39] In network synchronization, the algebraic connectivity \mu_2 governs the ease of phase-locking among coupled oscillators: larger \mu_2 (for fixed largest eigenvalue \mu_n) implies better synchronizability via a smaller eigenratio \mu_n / \mu_2, as seen in small-world networks where rewiring increases \mu_2 and enhances this property via Laplacian eigenvalues.^[40] Spectral clustering in machine learning uses the eigenvectors of L (or its normalized variants) to embed data points into a low-dimensional space for k-means partitioning, capturing nonlinear structures in similarity graphs effectively.^[41] Kirchhoff's matrix-tree theorem states that the number of spanning trees in G equals any cofactor of L, such as the determinant of the minor obtained by removing one row and column, providing an algebraic count of tree structures.^[42] For the path graph P_n on n vertices, the Laplacian eigenvalues are \mu_k = 2 - 2 \cos\left( \frac{\pi k}{n} \right) for k = 0, 1, \dots, n-1, with \mu_2 = 2 - 2 \cos\left( \frac{\pi}{n} \right) as the algebraic connectivity, illustrating how eigenvalues grow with path length.^[37] Post-2020 research has explored Laplacian eigenvalues in continuous-time quantum walks on graphs, where they drive unitary evolution for tasks like spatial search and state transfer, emerging as a tool in quantum algorithms on structured networks.^[43]

Invariant Polynomials

Chromatic Polynomial

The chromatic polynomial of a graph G, denoted P_G(t), is a monic polynomial of degree equal to the number of vertices in G that counts the number of proper vertex colorings of G using at most t colors, where a proper coloring assigns colors to vertices such that no adjacent vertices share the same color. Introduced by George David Birkhoff in 1912 as a tool to approach the four-color theorem for planar maps, the polynomial generalizes the concept of graph colorings to a continuous parameter t, allowing interpolation beyond integer values. A fundamental computational tool for the chromatic polynomial is the deletion-contraction recurrence, which states that for any edge e in G, P_G(t) = P_{G-e}(t) - P_{G/e}(t), where G-e is the graph obtained by deleting edge e and G/e is the graph obtained by contracting e (merging its endpoints and removing any resulting loops or multiple edges). This recurrence, established by Hassler Whitney in 1932, reduces the problem recursively until reaching base cases like edgeless graphs (where P_G(t) = t^n for n vertices) or graphs with loops (where P_G(t) = 0). It enables algorithmic computation but can be exponential in time complexity for dense graphs. The coefficients of P_G(t) exhibit strong structural properties: the sequence of absolute values of the coefficients is unimodal (increasing to a peak and then decreasing) and log-concave (satisfying a_k^2 \geq a_{k-1} a_{k+1} for coefficients a_k). Moreover, P_G(t) = 0 for all integers t < \chi(G), where \chi(G) is the chromatic number of G, the smallest number of colors needed for a proper coloring; this follows directly from the definition, as fewer colors than \chi(G) yield no proper colorings. These properties highlight the polynomial's role as an algebraic invariant capturing global coloring constraints. For the cycle graph C_n with n vertices, the chromatic polynomial is P_{C_n}(t) = (t-1)^n + (-1)^n (t-1), reflecting the bipartite nature for even n (\chi(C_n) = 2) and odd cycles requiring three colors. In contrast, for the complete graph K_n, P_{K_n}(t) = t(t-1)(t-2) \cdots (t-n+1), the falling factorial that directly encodes the sequential choice of distinct colors for each vertex. Whitney's broken cycle theorem provides a combinatorial expansion of the chromatic polynomial: P_G(t) = \sum_{A \subseteq E(G)} (-1)^{|A|} t^{c(A)}, where the sum is over subsets A of edges that contain no broken cycle (a cycle minus its maximum-labeled edge under a fixed edge ordering), and c(A) is the number of connected components in the subgraph induced by A. This theorem is particularly insightful for chordal graphs, which lack induced cycles of length greater than three; in such graphs, the absence of broken cycles aligns with perfect elimination orderings, yielding factorizations of P_G(t) into linear terms corresponding to clique sizes. The chromatic polynomial's development was motivated by the four-color problem, posed in 1852 by Francis Guthrie and resolved in 1976 by Kenneth Appel and Wolfgang Haken using computer-assisted case analysis; Birkhoff's polynomial offered early bounds showing P_G(5) > 0 for planar G, supporting \chi(G) \leq 4. Isomorphic graphs share identical chromatic polynomials, as colorings are preserved under isomorphism. However, non-isomorphic graphs can have the same P_G(t)—for instance, all trees on n vertices have P_G(t) = t(t-1)^{n-1}—and characterizing all pairs of graphs with matching polynomials remains an open problem. The chromatic polynomial generalizes to the Tutte polynomial, which encompasses broader subgraph counting invariants (detailed in a later section).

Matching and Tutte Polynomials

The matching polynomial of a graph G with n vertices is defined as \alpha_G(t) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k m_k t^{n-2k}, where m_k denotes the number of k-matchings in G.^[44] This polynomial encodes the number of matchings of various sizes in the graph, providing a combinatorial invariant that captures structural information about edge-disjoint selections. Unlike the characteristic polynomial, which arises from eigenvalues, the matching polynomial emphasizes matching configurations and satisfies a recurrence: for any edge e = \{u, v\} that is not a loop, \alpha_G(t) = \alpha_{G-e}(t) - t^2 \alpha_{G - u - v}(t).^[45] A key property of the matching polynomial is given by the Heilmann-Lieb theorem, which states that all roots of \alpha_G(t) are real and lie in the interval [-2\sqrt{\Delta-1}, 2\sqrt{\Delta-1}], where \Delta is the maximum degree of G.^[46] This real-rootedness has implications for the independence polynomial, as the matching polynomial of G corresponds to the independence polynomial of the line graph L(G), up to a variable substitution, thereby relating root locations to independence structures in the transformed graph.^[47] The Tutte polynomial generalizes several graph invariants, including the matching polynomial in certain evaluations, and is defined for a graph G with edge set E as T_G(x,y) = \sum_{A \subseteq E} (x-1)^{r(E) - r(A)} (y-1)^{|A| + k(A) - r(A)}, where the sum is over all subsets A of edges, r(\cdot) is the rank function of the cycle matroid (the size of a maximum forest in the subgraph induced by the subset), and k(A) is the number of connected components in that subgraph.^[48] This bivariate polynomial unifies counting problems across subgraphs and satisfies deletion-contraction relations: if e is a bridge, then T_G(x,y) = x \, T_{G/e}(x,y); if e is a loop, T_G(x,y) = y \, T_{G-e}(x,y); and if e is an ordinary edge, T_G(x,y) = T_{G-e}(x,y) + T_{G/e}(x,y).^[49] One notable evaluation is T_G(1,1), which equals the number of spanning trees in G, connecting the polynomial to Kirchhoff's matrix-tree theorem.^[48] The Tutte polynomial also encodes the chromatic polynomial as a special case: P_G(t) = (-1)^{|V| - k(G)} t^{k(G)} T_G(1-t, 0), where k(G) is the number of connected components of G.^[48] For example, in the Petersen graph, which has 10 vertices and 15 edges, the Tutte polynomial reflects its symmetric structure under duality in some evaluations.^[50] Applications of the Tutte polynomial extend to network reliability, where the reliability polynomial R_G(p), giving the probability that G remains connected when each edge fails independently with probability $1-p, can be expressed as R_G(p) = p^{n-1} T_G(1 + \frac{1-p}{p}, 1).^[51] In statistical mechanics, the Tutte polynomial serves as the partition function for the Potts model, with Z = \sum_{\sigma} \prod_{\{i,j\} \in E} e^{\beta J \delta_{\sigma_i \sigma_j}} = Q^{k(G)} T_G(1 + Q (e^{\beta J} - 1), e^{\beta J}) for Q states, enabling analysis of phase transitions; post-2020 developments in quantum and non-equilibrium extensions remain an active area but are beyond basic combinatorial scope here.^[49]

Advanced Branches

Cayley Graphs

A Cayley graph provides a graphical representation of an abstract group, encoding its multiplication structure through vertices and edges derived from a generating set. Formally, for a group \Gamma and a symmetric subset S \subseteq \Gamma \setminus \{e\} that generates \Gamma, the Cayley graph \operatorname{Cay}(\Gamma, S) has vertex set \Gamma and an undirected edge between distinct vertices g and h if h = g s for some s \in S.^[52] The graph is connected because S generates \Gamma, and it is regular of degree |S|, with each vertex adjacent to exactly |S| others.^[52] Key properties of Cayley graphs stem from the group's action on itself. They are vertex-transitive: the left multiplication by any group element \gamma \in \Gamma induces a graph automorphism that maps any vertex g to \gamma g, preserving adjacency since \gamma g \cdot s = \gamma (g s).^[52] The diameter of \operatorname{Cay}(\Gamma, S) equals the maximum, over all g \in \Gamma, of the shortest word length representing g as a product of elements from S \cup S^{-1}, measuring the graph's "spread" in terms of generator steps.^[53] Several theorems highlight the algebraic significance of Cayley graphs. A fundamental result characterizes them structurally: a connected graph is a Cayley graph if and only if it admits a group acting regularly (freely and transitively) on its vertices via automorphisms.^[54] Moreover, Cayley graphs realize any finite group \Gamma as the full automorphism group of some graph, specifically through appropriately chosen (possibly edge-colored) generating sets where the automorphism group coincides exactly with the left regular action of \Gamma.^[55] Regarding expansion, random Cayley graphs on non-abelian simple groups with suitable random generating sets S are expanders, meaning small vertex sets have many neighbors; explicit constructions, such as those from \mathrm{SL}_2(\mathbb{F}_p), yield Ramanujan graphs achieving the optimal spectral gap bound $2\sqrt{d-1} for degree d.^[56] Illustrative examples clarify these concepts. The symmetric group S_3 on three letters, with |S_3| = 6 and S all five non-identity elements (transpositions and 3-cycles), yields \operatorname{Cay}(S_3, S) \cong K_6, the complete graph on six vertices, which is 5-regular and fully connected.^[57] Another canonical case is the n-dimensional hypercube Q_n, isomorphic to \operatorname{Cay}((\mathbb{Z}/2\mathbb{Z})^n, \{e_i : 1 \leq i \leq n\}), where vertices are binary strings of length n and edges flip one bit, forming a connected n-regular graph.^[52] Cayley graphs find applications in coding theory, where their expander properties enable constructions of efficient error-correcting codes; for instance, expander codes built from Cayley graphs of groups like \mathrm{PGL}_2(\mathbb{F}_q) achieve good rate and distance with local testability.^[58] In the 2020s, group actions underlying Cayley graphs have informed cryptographic protocols.^[59]

Association Schemes

Association schemes provide a coherent algebraic framework for studying regular graphs and their relational structures, generalizing the notion of distance relations in graphs to multiple classes of associations. Formally, an association scheme on a finite set X with v = |X| vertices consists of a partition of the set of ordered pairs X \times X into r symmetric relations R_0, R_1, \dots, R_{r-1}, where R_0 is the identity relation \{(x,x) \mid x \in X\}, and for each i = 1, \dots, r-1, the relation R_i is such that the number of vertices y \in X adjacent to both a fixed x via R_i and a fixed z \neq x via R_j is constant, denoted by the intersection number p_{ij}^k, independent of the choice of x, z.^[60] The corresponding adjacency matrices A_i (with (A_i)_{xy} = 1 if (x,y) \in R_i and 0 otherwise) satisfy A_0 = I, \sum_{i=0}^{r-1} A_i = J (the all-ones matrix), and the multiplication rule A_i A_j = \sum_{k=0}^{r-1} p_{ij}^k A_k, forming a commutative algebra known as the Bose-Mesner algebra.^[60] This algebra is closed under both ordinary matrix multiplication and the Hadamard (entrywise) product, enabling the simultaneous diagonalization of all A_i by a common set of orthogonal idempotents E_0, \dots, E_{r-1}.^[60] Key properties of association schemes arise from their eigenspaces and character table. The eigenvalues of the scheme are given by the entries P_{ji} of the character table P, where the j-th eigenvalue of A_i is P_{ji}, and the multiplicities m_j satisfy \sum_j m_j P_{ji} = v_i (the valency, or degree of R_i).^[60] The dual eigenvalues Q_{ij} from the dual character table Q relate the idempotents via E_j = \frac{1}{v} \sum_i Q_{ji} A_i, and both tables satisfy orthogonality relations ensuring integrality of multiplicities m_j = \frac{v}{r} \sum_i Q_{ji}.^[60] A prominent example is a 2-class association scheme, which corresponds to a strongly regular graph: here, r=2, with parameters (v, k, \lambda, \mu) where k is the degree, \lambda = p_{11}^1, and \mu = p_{12}^1 = p_{21}^1 = p_{22}^1, and the eigenvalues are integers derived from the quadratic formula \theta = \frac{(\lambda - \mu) + \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}{2}.^[60] Significant theorems in association scheme theory include Delsarte's linear programming bound, which provides upper bounds on the size of codes or subsets with restricted intersections in the scheme. Specifically, for a subset C \subseteq X avoiding certain relations, the bound optimizes a linear program over nonnegative functions f on the classes satisfying \sum_i f_i A_i \succeq 0 (positive semidefinite in the eigenspaces) and derives |C| \leq v \cdot f(0), with equality conditions linked to tight designs.^[61] Existence of an association scheme also requires integrality conditions, such as nonnegative integer Krein parameters q_{ij}^k from the dual multiplication table and integer eigenvalues ensuring the scheme's parameters are feasible, as verified through the orthogonality of P and Q.^[60] Illustrative examples highlight the theory's applicability. The Petersen graph forms a 2-class association scheme as a strongly regular graph with parameters (10, 3, 0, 1), where each vertex has degree 3, adjacent vertices share no common neighbors (\lambda=0), and nonadjacent vertices share exactly one (\mu=1), with eigenvalues 3 (multiplicity 1), 1 (multiplicity 5), and -2 (multiplicity 4).^[60] Lattice graphs, such as those in the Hamming scheme H(d,q) on the vector space \mathbb{F}_q^d, partition pairs by Hamming distance, yielding intersection numbers p_{ij}^k = \binom{d-i}{k-i} \binom{i}{j-k} (q-1)^{j-k} for k \geq j \geq i, which model error-correcting codes in finite geometries.^[60] Advanced developments connect association schemes to broader structures, including coherent configurations, where the Bose-Mesner algebra generalizes to noncommutative cases but retains the partition and intersection properties for relational databases in combinatorics.^[60] Distance-regular graphs, such as the Petersen graph, embed as metric association schemes where intersection numbers depend only on distance differences, facilitating intersection arrays and diameter bounds.^[60] Recent links to quantum information theory, though underexplored, extend schemes to quantum graphs via operator algebras, defining quantum association schemes with noncommuting relations.^[62] These connections underscore schemes' role in diagonalizing multiple adjacency matrices beyond single-graph spectra.^[60]

References

[1]
[PDF] Spectral and Algebraic Graph Theory - Computer Science
This book is about how combinatorial properties of graphs are related to algebraic properties of associated matrices, as well as applications of those ...
[2]
[PDF] An Introduction to Algebraic Graph Theory - SUNY Geneseo
Mar 25, 2021 · In this book, we consider only finite graphs. A graph can be used to encode some relationship of interest between entities. The entities are ...
[3]
[PDF] Introduction to Algebraic Graph Theory 1 The characteristic ...
The spectrum of a graph G is the set of eigenvalues of A(G) together with their multiplicities. Since A (short for A(G)) is a real symmetric matrix, basic ...
[4]
[PDF] Graph Theory: Penn State Math 485 Lecture Notes
(5) Algebraic Graph Theory: Is the application of abstract algebra (sometimes associ- ... Definition 9.18 (First Order Theory of Graphs). In the first ...
[5]
[PDF] Spectral and Algebraic Graph Theory - Jason Cantarella
This book is about how combinatorial properties of graphs are related to algebraic properties of associated matrices, as well as applications of those ...
[6]
[PDF] A Study in Algebraic Graph Theory
May 1, 2021 · Algebraic graph theory applies algebraic methods to graph problems, using tools for proofs and studying the spectrum of adjacency or Laplacian ...
[7]
[PDF] Introduction to Graph Theory - FSU Math
Definition 1.1.1. A simple graph (V,E) consists of a nonempty set represent- ing vertices, V , and a set of unordered pairs of elements of V representing edges ...
[8]
[PDF] graph theory: basic definitions and theorems
A graph with more than one edge between a pair of vertices is called a multigraph while a graph with loop edges is called a pseudograph.
[9]
[PDF] Math 2331 – Linear Algebra - 4.1 Vector Spaces & Subspaces
A vector space is a nonempty set V of objects, called vectors, on which are defined two operations, called addition and multiplication by scalars (real numbers) ...
[10]
[PDF] Chapter 1: Abstract Group Theory - Rutgers Physics
Basic Definitions. We begin with the abstract definition of a group. Definition 2.1: A group G is a set with a multiplication: ∀a, b ∈ G there exists a ...
[11]
Ueber die Auflösung der Gleichungen, auf welche man bei der ...
Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. G. Kirchhoff,.Missing: original paper
[12]
On the Geographical Problem of the Four Colours - jstor
On the Geographical Problemii of the Four Colours. BY A. B. KEMPE, B. A., London, England. IF we examine any ordinary map, we shall find in general ...
[13]
Desiderata and Suggestions: No. 2. The Theory of Groups - jstor
DESIDERATA AND SUGGESTIONS. BY PROFESSOR CAYLEY, Cambridqe, Enqland. No. 2.-THE THEORY OF GROUPS: GRAPHICAL REPRESENTATION.
[14]
Algebraic Graph Theory and Quantum Computing | Fields Institute ...
This course will provide an introduction to problems in quantum computing that can be studied using tools from algebraic graph theory.Missing: 2020 | Show results with:2020
[15]
Graph neural networks: A review of methods and applications
Graph neural networks (GNNs) are neural models that capture the dependence of graphs via message passing between the nodes of graphs.
[16]
[PDF] Chapter 1. Graphs
Feb 20, 2023 · The adjacency matrix of G is the n × n matrix (where n = v(G)) AG = (auv), where auv is the number of edges joining vertices u and v, each loop ...
[17]
[PDF] Graph Theory - UMD MATH
Jul 21, 2021 · For a simple graph G the adjacency matrix is the sym- metric matrix A such that aij equals 1 if vertices i and j are connected by an edge and 0 ...
[18]
[PDF] Matrices and Graphs 12.1 The Adjacency Matrix and Counting ...
The adjacency matrix A of a graph with n vertices is the n × n matrix with entry aij = 1 if vertex i and j are adjacent and 0 otherwise. Recall that in a walk ...
[19]
[PDF] Chapter 17 Graphs and Graph Laplacians - UPenn CIS
Remark: Some authors adopt the opposite convention of sign in defining the incidence matrix, which means that their incidence matrix is B. Page 5. 17.1.
[20]
[PDF] Connectivity in graphs 1 Graphs and incidence matrices
We'll see that graph-theoretic connectivity properties of a graph will have linear algebraic implications for its incidence matrix. Moreover, a linear algebraic ...<|control11|><|separator|>
[21]
[PDF] Graph Theory Fundamentals - FSU Math
The adjacency matrix for a graph is n X n and each element contains 0 for non-neighbors and the edge weight for neighbors. A = Page 5.
[22]
Graph Automorphism -- from Wolfram MathWorld
The automorphism groups of a graph characterize its symmetries, and are therefore very useful in determining certain of its properties. The group of graph ...
[23]
Graphs of Degree Three with a Given Abstract Group
Nov 20, 2018 · A given abstract group be represented as the group of the automorphisms of a (finite) graph, and if possible how can the graph be constructed?
[24]
The Automorphism Group of the Petersen Graph is Isomorphic to $S_5
Dec 5, 2020 · The automorphism group of the Petersen Graph is shown to be isomorphic to the symmetric group on 5 elements.Missing: 120 | Show results with:120
[25]
(PDF) The Schreier-Sims algorithm - ResearchGate
This representation helps us to calculate the grouporder, list the group elements, generate random elements, test for group mem-bership and store group elements ...
[26]
Cayley graphs with few automorphisms: the case of infinite groups
Oct 12, 2020 · Abstract:We characterize the finitely generated groups that admit a Cayley graph whose only automorphisms are the translations, confirming a ...
[27]
[PDF] Spectra of graphs - CWI
More in particular, spectral graph theory studies the relation between graph properties and the spectrum of the adjacency matrix or Laplace matrix. And the ...
[28]
[PDF] Lecture 3 1 Eigenvalue Identities
Aug 30, 2016 · Theorem 4 (Perron-Frobenius) Let G be a connected graph with adjacency matrix A, eigenvalues λ1 ≥ λ2 ≥···≥ λn and corresponding ...
[29]
[PDF] Algebraic Graph Theory - CMU School of Computer Science
One of the main problems of algebraic graph theory is to determine precisely how, or whether, properties of graphs are reflected in the algebraic properties of ...
[30]
[PDF] The Perron-Frobenius theorem.
The adjacency matrix A of the graph (V,E) is the n × n matrix (where n is the number of nodes) with Aij =1if(vj,vi) ∈ E and = 0 otherwise. So if (V,E) is ...
[31]
[PDF] On Moore Graphs with Diameters 2 and 3
Abstract: This note treats the existence of connected, undirected graphs homogeneous of degree cI and of diameter Ie, having a number of nodes which is ...Missing: paper | Show results with:paper
[32]
[PDF] Moore graphs and beyond: A survey of the degree/diameter problem
The study of Moore graphs was initiated by Hoffman and Singleton. Their pioneering paper [160] was devoted to Moore graphs of diameter 2 and 3. In the case ...
[33]
Petersen Graph -- from Wolfram MathWorld
162). The Petersen graph is an integral graph with graph spectrum (-2)^41^53^1 . The bipartite double graph of the Petersen graph is the Desargues graph.Missing: source | Show results with:source
[34]
(PDF) Hoffman's ratio bound - ResearchGate
Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix.<|separator|>
[35]
The spectrum of a graph (Chapter 2) - Algebraic Graph Theory
The spectrum of a graph · Norman Biggs, London School of Economics and Political Science; Book: Algebraic Graph Theory; Online publication: 05 August 2012 ...
[36]
None
### Summary of Laplacian Matrix, Spectrum Properties, and Path Graph Example
[37]
[PDF] Algebraic connectivity of graphs. - SNAP: Stanford
We shall call the second smallest eigenvalue a(G) of the matrix A(G) algebraic connectivity of the graph G. It is the purpose of this paper to find its relation ...
[38]
[PDF] Four proofs for the Cheeger inequality and graph partition algorithms
We will give four proofs of the Cheeger inequality which relates the eigenvalues of a graph with various isoperimetric variations of the. Cheeger constant.
[39]
Synchronization in Small-World Systems | Phys. Rev. Lett.
We quantify the dynamical implications of the small-world phenomenon by considering the generic synchronization of oscillator networks of arbitrary topology.
[40]
On Spectral Clustering: Analysis and an algorithm - NIPS papers
In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation ...
[41]
[PDF] Kirchhoff's matrix-tree theorem
May 29, 2024 · The theorem can be stated as follows: take an unoriented graph and turn it into a special matrix called Laplacian. Its diagonal contains degrees ...
[42]
Quantum Walk Computing: Theory, Implementation, and Application
Nov 13, 2024 · In this review, we provide a thorough summary of quantum walks and quantum walk computing, including theories and characteristics, physical implementations, ...
[43]
Matching Polynomial -- from Wolfram MathWorld
A k-matching in a graph G is a set of k edges, no two of which have a vertex in common (ie, an independent edge set of size k).
[44]
[PDF] Matching Polynomials of Graphs 26.1 Overview 26.2 2 √ d − 1
Dec 5, 2018 · The coefficients of the matching polynomial of a graph count the numbers of matchings of various sizes in that graph. It was first defined ...
[45]
[2206.09558] A hypergraph Heilmann--Lieb theorem - arXiv
Jun 20, 2022 · The Heilmann--Lieb theorem is a fundamental theorem in algebraic combinatorics which provides a characterization of the distribution of the zeros of matching ...
[46]
Generalizations of the Matching Polynomial to the Multivariate ...
We generalize two main theorems of matching polynomials of undirected simple graphs, namely, real-rootedness and the Heilmann–Lieb root bound.
[47]
Tutte Polynomial -- from Wolfram MathWorld
The Tutte polynomial is therefore a rather general two-variable graph polynomial from which a number of other important one- and two-variable polynomials can be ...
[48]
[PDF] The Tutte polynomial - UC Davis Math
1. INTRODUCTION. The Tutte polynomial is a polynomial in two variables x; y which can be defined for a graph, matrix, or, even more generally, a matroid.
[49]
Tutte polynomial - Graph Theory - SageMath Documentation
The Tutte polynomial of the Petersen graph is: Sage. sage: P = graphs.PetersenGraph() sage: P.tutte_polynomial() x^9 + 6*x^8 + 21*x^7 + 56*x^6 + 12*x^5*y + y ...
[50]
[PDF] Graph Polynomials and Their Applications I: The Tutte ... - arXiv
Jun 28, 2008 · The Tutte polynomial may be defined by a linear recursion relation given by deleting and contracting ordinary edges. The “most simple” terminal ...
[51]
[PDF] CAYLEY GRAPHS Definition 1.1. Let H be a finite group and let S ...
In this short note we give an introduction to some elementary properties of Cayley graphs.The first section covers the definition and gives some basic ...
[52]
On the diameter of permutation groups - Annals of Mathematics
diam(Γ(G,A)) of the Cayley graph Γ(G,A) is the smallest ℓ such that every element of G can be expressed as a word of length at most ℓ in A∪A−1. We are concerned ...
[53]
[PDF] Structural characterization of Cayley graphs - arXiv
Sep 27, 2016 · We can characterize the Cayley graphs as vertex-transitive graphs. By definition, any Cayley graph satisfies three basic graph properties.
[54]
Realizing groups as automorphism groups of graphs. - MathOverflow
Sep 1, 2010 · The argument basically is that a group is the automorphism group of its (colored) Cayley graph and that the colors of edge in the Cayley graph ...Is there any relation between automorphism group of a Cayley ...Applications of infinite graph theory - MathOverflowMore results from mathoverflow.net
[55]
[PDF] Random Cayley Graphs and Expanders - Math (Princeton)
Feb 22, 2002 · Ramanujan graphs. (As shown in [Al1] they can be Ramanujan graphs for degrees which are about the square root of the number of vertices.).
[56]
[PDF] THE PRIME ORDER CAYLEY GRAPH - UPB
In this example we present some groups and associated prime order. Cayley graphs. (i) Cayley(S3, S) is complete 5-regular graph K6 ,where S3 is symmetric.
[57]
[PDF] Expander Codes and Their Construction via Cayley Graphs
May 20, 2025 · 3.2.2 Properties of Cayley Graphs ... • Ramanujan graphs represent the gold standard for expander graphs, achieving the theoretical optimal.
[58]
[PDF] Cryptographic Group Actions and Applications
Sep 28, 2020 · In this work, we propose a new framework based on group actions that enables the easy usage of a variety of isogeny-based assumptions. Our ...
[59]
[PDF] Association Schemes - University of Waterloo
Jun 3, 2010 · These notes provide an introduction to association schemes, along with some related algebra.
[60]
[PDF] An algebraic approach to the association schemes of coding theory
DELSARTE. ') Thesis, Universite Catholique de Louvain, June 1973. Promoter: Professor Dr J. M. Goethals. Philips Res. Repts Suppl. 1973, No. 10. Page 2 ...
[61]
[2404.06157] Quantum association schemes - arXiv
Apr 9, 2024 · We introduce quantum association schemes. This allows to define distance regular and strongly regular quantum graphs. We bring examples thereof.Missing: information theory 2020