SRGs

SRGs, or strongly regular graphs, are a special class of graphs in combinatorics with a high level of uniformity in the neighborhoods of pairs of vertices. An SRG is specified by four parameters (v, k, λ, μ): it has v vertices, is k-regular, every pair of adjacent vertices has exactly λ common neighbors, and every pair of non-adjacent vertices has exactly μ common neighbors.

A key feasibility condition for SRGs is the equation (v − k − 1) μ = k (k − λ − 1). This relation must hold for the parameters to describe a possible SRG. Spectrally, an SRG has exactly three distinct eigenvalues: k, and two others r and s, given by r, s = 0.5[(λ − μ) ± sqrt((λ − μ)^2 + 4(k − μ))]. The eigenvalues provide deep insights into the graph’s structure and are used in construction and classification results.

Complementation also preserves the SRG property: the complement of an SRG(v, k, λ, μ) is an SRG with parameters (v, v − k − 1, v − 2 − 2k + μ, v − 2k + λ).

Notable examples include the Petersen graph, which is SRG(10, 3, 0, 1); the 5-cycle C5, SRG(5, 2, 0, 1); the 4x4 rook graph, SRG(16, 6, 2, 4); and the Clebsch graph, SRG(16, 5, 0, 2). Many SRGs arise from combinatorial designs and finite geometries, and they play a central role in algebraic graph theory, coding theory, and the study of distance-regular graphs.