Fact-checked by Grok 2 weeks ago

Strongly regular graph

In graph theory, a strongly regular graph is a regular graph of degree k on n vertices such that every adjacent pair of distinct vertices has exactly \lambda common neighbors, and every non-adjacent pair of distinct vertices has exactly \mu common neighbors, where \lambda and \mu are fixed integers with $0 \leq \lambda < k and $0 \leq \mu < k.^[1] These parameters (n, k, \lambda, \mu) uniquely determine the structure up to isomorphism in many cases, though some parameter sets admit multiple non-isomorphic graphs.^[2] The concept was introduced by R. C. Bose in 1963 as a tool to study partial geometries and partially balanced incomplete block designs, linking graph theory to combinatorial design theory.^[1] Strongly regular graphs form the basic building blocks of 2-class association schemes and exhibit highly symmetric adjacency relations, making them a focal point in algebraic graph theory.^[2] The adjacency matrix of such a graph has exactly three distinct eigenvalues: the degree k (with multiplicity 1), and two others \theta and \tau given by the quadratic formula \frac{(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}{2}, whose multiplicities are integers determined by the parameters.^[2] Notable examples include the cycle graph C_5 (parameters (5,2,0,1)), the Petersen graph (parameters (10,3,0,1)), and the Hoffman-Singleton graph (parameters (50,7,0,1)), which are the three known Moore graphs of diameter 2 (a possible fourth of degree 57 remains unknown).^[2] These graphs satisfy stringent integrality conditions on their parameters, such as the parameter equation n = 1 + k + \frac{k(k - \lambda - 1)}{\mu} and the requirement that the eigenvalues have integer multiplicities, which constrain possible parameter sets and have led to extensive classification efforts.^[2] Strongly regular graphs arise in applications including error-correcting codes, network design, and quantum state discrimination, due to their regular spectral properties and combinatorial uniformity.^[3]^[4]

Definition and Parameters

Formal Definition

A strongly regular graph is a k-regular simple graph on n vertices such that every pair of adjacent vertices has exactly \lambda common neighbors, and every pair of non-adjacent vertices has exactly \mu common neighbors, where k, \lambda, and \mu are non-negative integers with $0 \leq \lambda \leq k-1, $0 \leq \mu \leq k, and $0 < k < n-1.^[2]^[5] Certain families of graphs satisfy this definition but are often classified as trivial cases and analyzed separately due to degenerate parameter values. The complete graph K_n (for n \geq 2) is strongly regular with parameters (n, n-1, n-2), but \mu is undefined since no non-adjacent pairs exist. The null graph (empty graph on n vertices) has degree k=0 and \mu=0, but \lambda is undefined due to the absence of adjacent pairs. The 5-cycle C_5 is strongly regular with parameters (5, 2, 0, 1), yet it is typically studied apart from other examples as the unique cycle graph exhibiting this property beyond trivial complete or disjoint unions.^[2]^[5] When \mu > 0, a connected strongly regular graph has diameter 2 and is distance-regular, meaning the number of vertices at distance i from a given vertex depends only on i.^[2]^[6] These graphs emerge prominently in design theory as the adjacency structures of symmetric balanced incomplete block designs (particularly when \lambda = \mu), in association schemes as symmetric two-class schemes generating a 3-dimensional Bose-Mesner algebra, and in spectral graph theory for their explicit eigenvalues and multiplicities derived from the parameters.^[7]^[6]

Parameters and Integrity Conditions

A strongly regular graph is characterized by four parameters: n, the number of vertices; k, the degree of each vertex (also called the valency); \lambda, the number of common neighbors shared by any two adjacent vertices; and \mu, the number of common neighbors shared by any two non-adjacent vertices.^[6] These parameters must satisfy certain basic integrity conditions to ensure the graph's existence and consistency. Specifically, since the graph is k-regular and not complete or null, $0 < k < n-1; additionally, \lambda and \mu are non-negative integers bounded by $0 \leq \lambda \leq k-1 and $0 \leq \mu \leq k, as the number of common neighbors cannot exceed the degree or be negative.^[6]^[1] The fundamental integrity condition linking these parameters is the equation

(n - k - 1)\mu = k(k - \lambda - 1).

This arises from a double-counting argument on the number of paths of length 2 in the graph. Fix a vertex x; it has k neighbors. For each neighbor y of x, there are exactly k - \lambda - 1 vertices adjacent to y but neither to x nor to itself (since y has k neighbors total, minus the edge to x and \lambda other common neighbors with x). Thus, the total number of such paths from x through its neighbors to non-neighbors is k(k - \lambda - 1). On the other hand, x has n - k - 1 non-neighbors (excluding itself), and each such non-neighbor z shares exactly \mu common neighbors with x, so the same count yields (n - k - 1)\mu. Equating these gives the condition.^[6] This equation ensures the consistency of neighbor counts across the graph and implies that n = 1 + k + \frac{k(k - \lambda - 1)}{\mu} when \mu > 0, providing an explicit expression for the order in terms of the other parameters. Violations lead to infeasible configurations; for instance, if \mu > k, the condition cannot hold since the left side would exceed possible path counts bounded by the right side, rendering such parameters impossible for any graph.^[6] Additional integrity conditions arise from the spectral properties. The adjacency matrix has eigenvalues k (multiplicity 1), and \theta, \tau = \frac{(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}{2} with multiplicities

f = \frac{1}{2} \left( (n-1) + \frac{ (n-1)(\mu - \lambda) + 2k }{ \sqrt{ (\lambda - \mu)^2 + 4(k - \mu) } } \right), \quad g = \frac{1}{2} \left( (n-1) - \frac{ (n-1)(\mu - \lambda) + 2k }{ \sqrt{ (\lambda - \mu)^2 + 4(k - \mu) } } \right).

The discriminant \Delta = (\lambda - \mu)^2 + 4(k - \mu) must be a perfect square (so \theta, \tau are integers), and f, g must be non-negative integers with f + g = n - 1.^[2]

Historical Background

Etymology

The term "strongly regular graph" was coined by R. C. Bose in his 1963 paper to describe a class of graphs that impose regularity conditions not only on vertex degrees but also on the number of common neighbors between pairs of vertices, distinguishing them from ordinary regular graphs where only degrees are uniform.^[1] This nomenclature highlights the enhanced structural uniformity, as the graphs satisfy that any two adjacent vertices share exactly λ common neighbors and any two non-adjacent vertices share exactly μ common neighbors, providing a stronger combinatorial constraint.^[1] The standard parameters (v, k, λ, μ)—representing the number of vertices, degree of each vertex, common neighbors for adjacent vertices, and common neighbors for non-adjacent vertices, respectively—stem from Bose's framework, which drew inspiration from partially balanced incomplete block designs and association schemes; the Greek letters λ and μ were chosen to denote the adjacency and non-adjacency relations in these schemes.^[1] Although Bose initially employed notation such as (v, n₁, n₂, p₁₁, p₂₁) in his definition, the (v, k, λ, μ) tuple quickly became the conventional parameterization in subsequent literature.^[1] Concepts akin to strongly regular graphs emerged in the 1950s through studies of lattice designs, which are specific partially balanced incomplete block designs with two associate classes, laying the groundwork for Bose's formal introduction of the term.^[8] The designation "strongly regular" thus contrasts with mere "regular" graphs, underscoring the additional relational regularity without overlap with other terminologies like weakly regular structures.^[1]

Key Developments

The roots of strongly regular graphs trace back to the 1950s in the study of association schemes and symmetric designs, where R. C. Bose and T. A. Shimamoto introduced concepts equivalent to two-class association schemes that underpin the structure of these graphs. This work connected combinatorial designs to algebraic frameworks, later formalized in the Bose-Mesner algebra, which analyzes the adjacency relations in such schemes.^[6] In 1963, R. C. Bose formally introduced the term "strongly regular graph" in his seminal paper, linking these graphs to partial geometries and partially balanced incomplete block designs with two associate classes.^[9] This formalization established strongly regular graphs as a key object in algebraic combinatorics, building directly on the association scheme foundations. During the 1960s and 1970s, significant advancements included A. J. Hoffman and R. R. Singleton's 1960 theorem on Moore graphs of diameter 2, which characterized strongly regular graphs achieving the Moore bound and identified the unique (50,7,0,1)-graph. This predated Bose's terminology but highlighted extremal properties. Contributions from R. M. Damerell in 1973 provided spectral bounds and existence constraints, ruling out certain parameter sets through eigenvalue analysis.^[6] Concurrently, J. J. Seidel advanced the field with 1968 work on graphs having smallest eigenvalue -2, introducing tools like the Seidel matrix for spectral characterizations. From the 1980s onward, the theory expanded into coding theory and computational enumeration, with the McLaughlin graph—a (275,112,30,56)-strongly regular graph discovered in 1969—finding applications in constructing optimal codes due to its association scheme structure. Computer-assisted searches became prominent, classifying known parameters and verifying nonexistence for many cases through exhaustive enumeration.^[6] In recent years up to 2025, computational methods have yielded new discoveries, such as the 2024 application (published 2025) of local search algorithms to partial difference sets, identifying partial difference sets with 62 different parameter values across 1254 nonisomorphic groups of order at most 147 and providing first known constructions for two new strongly regular graphs with parameters (144,52,16,20) and (147,66,25,33).^[10] These techniques, leveraging nonabelian group structures, have expanded the catalog of feasible parameters and reinforced connections to finite geometries.^[11]

Examples

Small Strongly Regular Graphs

The smallest non-trivial strongly regular graph is the 5-cycle C_5, which has parameters \mathrm{srg}(5,2,0,1).^[12] It can be constructed with vertices \{0,1,2,3,4\} and edges between i and j if j \equiv i \pm 1 \pmod{5}.^[12] This graph is also isomorphic to the Paley graph of order 5, formed as the quadratic residue graph over the finite field \mathbb{F}_5, where vertices are elements of \mathbb{F}_5 and edges connect pairs whose difference is a nonzero quadratic residue modulo 5 (namely, 1 and 4).^[13] The lattice graph L_2(3) is the unique strongly regular graph with parameters \mathrm{srg}(9,4,1,2).^[14] It is constructed on the vertex set

{{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}} \times {{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}}

, where two vertices (i,j) and (i',j') are adjacent if they share the same row (i=i') or the same column (j=j'), forming a $3 \times 3 grid graph under the rook adjacency rule.^[15] The Petersen graph is the unique triangle-free strongly regular graph of order 10, with parameters \mathrm{srg}(10,3,0,1).^[16] It can be constructed as the odd graph O_3, whose vertices are the 2-element subsets of a 5-element set \{1,2,3,4,5\}, with edges between disjoint subsets.^[17] Alternatively, it is the complement of the line graph of the complete graph K_5.^[16] The Hoffman-Singleton graph is the unique Moore graph of diameter 2 and degree 7, with parameters \mathrm{srg}(50,7,0,1).^[18] It admits constructions via voltage graphs lifted from the Petersen graph or using incidence structures derived from finite geometries akin to projective planes, though no projective plane of order 7 exists.^[19] The Gewirtz graph is the unique strongly regular graph with parameters \mathrm{srg}(56,10,0,2).^[20] It can be constructed using the ternary Golay code as the graph on the 56 octads containing two given symbols a, b but not a third symbol c, where two octads are adjacent if they intersect in exactly \{a, b\}.

Infinite Families and Constructions

One prominent infinite family of strongly regular graphs is the Paley graphs. For a prime power q \equiv 1 \pmod{4}, the Paley graph of order q has parameters (q, (q-1)/2, (q-5)/4, (q-1)/4) and is constructed on the vertices of the finite field \mathbb{F}_q, with an edge between distinct elements x and y if x - y is a nonzero quadratic residue in \mathbb{F}_q. This construction, introduced by Paley in connection with orthogonal matrices, yields self-complementary graphs that are also conference graphs.^[21] Another classical infinite family consists of the lattice graphs L_2(n), or equivalently the rook's graphs R_n, for integers n \geq 2. These graphs have n^2 vertices corresponding to the squares of an n \times n chessboard, with edges between vertices that share a row or column (modeling rook moves). They are strongly regular with parameters (n^2, 2(n-1), n-2, 2) and arise as the line graphs of the complete bipartite graphs K_{n,n}. The Cartesian product structure underlies their regularity and the specific intersection properties of adjacent and nonadjacent vertices. The Shrikhande graph provides a key example of a near-lattice construction, with parameters (16, 6, 2, 2), matching those of the $4 \times 4 lattice graph L_2(4) but differing in structure. Constructed using modifications to the L_2 association scheme via nonstandard Latin squares, it demonstrates non-uniqueness for these parameters and is one of four non-isomorphic strongly regular graphs sharing them. Variants of this approach, including other distance-regular graphs on 16 vertices, extend the lattice family by altering the relation matrices in Bose-Mesner algebras while preserving the parameters. Constructions related to sporadic simple groups, such as precursors to the McLaughlin graph family, draw from block designs like the Witt design W_{12}. The McLaughlin graph itself, with parameters (275, 112, 30, 56), emerges as the collinearity graph of a 4-(23,7,1) design extended by group actions, highlighting how symmetric designs yield strongly regular graphs with high symmetry. These methods generalize to other finite geometries tied to exceptional groups, focusing on incidence structures rather than explicit group orders. General construction techniques for infinite families include Cayley graphs on abelian groups, where the connection set forms a partial difference set to ensure the strongly regular condition. For an abelian group G of order v and a subset D \subset G with |D| = k satisfying specific difference equations, the Cayley graph \mathrm{Cay}(G, D) is strongly regular with parameters determined by the multiset of differences in D - D. Equitable partitions further enable derivations: partitioning the vertex set of a known strongly regular graph into equitable classes (where neighbor counts are constant across classes) produces quotient graphs that inherit strong regularity. Recent advancements have uncovered new infinite families through computational methods. In 2024, local search algorithms identified partial difference sets in 1254 nonisomorphic groups of order at most 147, generating 62 distinct parameter sets for strongly regular graphs via Cayley constructions; many of these sets were previously unknown or unverified, expanding the feasible parameter space.^[10]

Special Classes

Strongly regular graphs form several special classes defined by additional constraints on their parameters or structural properties. One prominent class consists of triangle-free strongly regular graphs, where λ = 0, meaning no two adjacent vertices share a common neighbor. In such graphs, the parameters satisfy the relation k(k - 1) = (v - k - 1)μ, derived from the standard counting condition for the number of paths of length two between vertices. Representative examples include the Petersen graph with parameters (10, 3, 0, 1) and the Hoffman-Singleton graph with parameters (50, 7, 0, 1), both of which are unique for their respective parameter sets.^[6] Another special class is that of geodetic strongly regular graphs, where μ = 1, ensuring that every pair of vertices at distance 2 has exactly one common neighbor and thus a unique shortest path of length 2. This property implies the graph is geodetic, with diameter 2, and includes the Moore graphs of diameter 2 as extremal cases achieving the Moore bound v = 1 + k^2. Known examples are the cycle graph C_5 with parameters (5, 2, 0, 1), the Petersen graph (10, 3, 0, 1), and the Hoffman-Singleton graph (50, 7, 0, 1); however, existence remains unknown for certain parameter sets beyond these, such as (3250, 57, 0, 1) and the potential (400, 21, 2, 1).^[6]^[22] Locally linear strongly regular graphs, characterized by λ = 1, have the property that every edge lies in exactly one triangle, as adjacent vertices share precisely one common neighbor. This structure relates to linear spaces in combinatorial design theory, where the triangles can be viewed as blocks covering pairs uniquely. Conference graphs form yet another distinct class of strongly regular graphs with parameters (4μ + 1, 2μ, μ - 1, μ) for some integer μ ≥ 1, arising from conference matrices and linked to symmetric (2-(4μ + 1, 2μ + 1, μ)) designs. Examples include the Paley graph of order 5, which is the cycle C_5.^[23] Uniqueness results hold for many small parameter sets within these classes; for instance, the Petersen graph is the unique strongly regular graph with parameters (10, 3, 0, 1), and the Hoffman-Singleton graph is unique with (50, 7, 0, 1).

Algebraic Properties

Parameter Relationships

A fundamental parameter relationship in strongly regular graphs arises from a combinatorial counting argument applied to paths of length 2 between vertices. Consider a fixed vertex x with degree k. The number of vertices adjacent to x is k, and among the remaining v - k - 1 non-adjacent vertices, each shares exactly \mu common neighbors with x. Thus, the total number of such paths is (v - k - 1)\mu. Alternatively, counting from the neighbors of x, each of the k neighbors contributes k - \lambda - 1 paths to non-adjacent vertices (excluding x and the \lambda mutual neighbors). This yields the equation

k(k - \lambda - 1) = (v - k - 1)\mu.

This relation, derived in early combinatorial studies of regular graphs, serves as a necessary condition for the parameters to be feasible and is used to express one parameter in terms of the others.^[24] Additional counting arguments reveal further structural insights. The total number of edges in the graph is \frac{1}{2} v k, reflecting the regularity. For triangles, fix a vertex x; its neighborhood induces a \lambda-regular graph on k vertices, so the number of edges within this neighborhood is \frac{1}{2} k \lambda. Each such edge, together with x, forms a triangle, giving exactly \frac{1}{2} k \lambda triangles incident to x. These counts emphasize the uniform local structure inherent to strongly regular graphs.^[24] Krein parameters q_{i,j} provide another layer of interrelations by counting the number of walks of length 4 between vertices in specific eigenspaces of the association scheme, ensuring non-negativity for feasibility. These parameters impose absolute bounds on the existence of the graph, such as inequalities involving the eigenvalues and multiplicities, but detailed computations are deferred to spectral analyses.^[25] Feasibility beyond the basic integrity conditions requires the eigenvalues to be algebraic integers with integer multiplicities. While many strongly regular graphs have integer eigenvalues (requiring the discriminant \Delta = (\lambda - \mu)^2 + 4(k - \mu) to be a perfect square), some have irrational eigenvalues, such as the cycle graph C_5 with parameters (5,2,0,1). Determinant conditions on the intersection matrix further constrain existence, ensuring non-negative Krein parameters and positive integrality.^[24] A notable special case occurs when \lambda = \mu. Substituting into the fundamental equation gives k(k - \lambda - 1) = (v - k - 1)\lambda, and the adjacency matrix satisfies A^2 = (k - \lambda)I + \lambda J. In this scenario, the graph corresponds to the incidence structure of a symmetric 2-(v, k, \lambda) design, where the adjacency matrix aligns with the design's incidence matrix properties. Examples include the Shrikhande graph with parameters (16, 6, 2, 2).^[25]

Adjacency Matrix Equations

The adjacency matrix A of a strongly regular graph with parameters (v, k, \lambda, \mu) is a symmetric v \times v matrix with entries in \{0, 1\}, zeros on the main diagonal, and A_{ij} = 1 if and only if vertices i and j are adjacent. This matrix satisfies the equation

A^2 = k I + \lambda A + \mu (J - I - A),

where I is the identity matrix and J is the all-ones matrix.^[6] The equation derives from counting walks of length 2 in the graph: the (i,j)-entry of A^2 equals the number of common neighbors of vertices i and j. When i = j, this count is k, the common degree of all vertices. When i \neq j, the count is \lambda if i and j are adjacent (so A_{ij} = 1) and \mu otherwise (so A_{ij} = 0). Substituting these cases into the off-diagonal entries of A^2 and solving for the matrix equation yields the relation above.^[6] Multiplying both sides of the equation by A expresses A^3 as a linear combination of I, A, and J, implying that all higher powers of A lie in the span of \{I, A, J\}. Consequently, the minimal polynomial of A has degree at most 3.^[6] This cubic relation often determines the graph up to isomorphism from its parameters (v, k, \lambda, \mu) in many cases, as the algebraic structure constrains the possible realizations.^[26] Strongly regular graphs are precisely the connected graphs underlying symmetric 2-class association schemes, in which the Bose-Mesner algebra—the commutative \mathbb{R}-algebra generated by the association matrices I, A, and J - I - A—has dimension 3.^[27]

Eigenvalues and Spectrum

The adjacency matrix of a strongly regular graph with parameters (v, k, \lambda, \mu) has eigenvalue k with multiplicity 1, corresponding to the all-ones eigenvector.^[6] The remaining eigenvalues consist of two distinct values, [\theta](/page/Theta) (positive) and [\tau](/page/Tau) (negative), which are the roots of the quadratic equation x^2 - (\lambda - \mu)x + (\mu - k) = 0.^[25] Explicitly,

\theta, \tau = \frac{(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}{2},

where \theta > 0 > \tau.^[6] The multiplicities f of \theta and g of \tau are given by

f = \frac{1}{2} \left[ (v-1) - \frac{((v-1)(\lambda - \mu) + 2k)}{\sqrt{\Delta}} \right], \quad g = \frac{1}{2} \left[ (v-1) + \frac{((v-1)(\lambda - \mu) + 2k)}{\sqrt{\Delta}} \right],

with \Delta = (\lambda - \mu)^2 + 4(k - \mu) and f + g = v - 1.^[6] These multiplicities must be non-negative integers, serving as a necessary condition for the existence of a strongly regular graph with the given parameters.^[25] The spectrum of the graph is denoted as (k^1, \theta^f, \tau^g), encapsulating the full eigenvalue structure.^[6] This spectral information is central to spectral graph theory, enabling applications such as bounding the number of vertices via eigenvalue interlacing.^[25] For example, the Petersen graph, with parameters (10, 3, 0, 1), has spectrum (3^1, 1^5, (-2)^4).^[6]

Theorems and Bounds

Hoffman-Singleton Theorem

The Hoffman-Singleton theorem provides a complete classification of Moore graphs of diameter 2, which are regular graphs of degree k and girth 5 achieving the Moore bound on the number of vertices, v = 1 + k + k(k-1) = 1 + k^2. These graphs are strongly regular with parameters (v, k, 0, 1). The theorem states that such a graph exists only for k = 2, 3, 7, or $57, corresponding to v = 5, 10, 50, or $3250, respectively. The existence for k=57 remains open as of 2025.^[28] The proof relies on the spectral properties of strongly regular graphs. For parameters \lambda = 0 and \mu = 1, the nontrivial eigenvalues are the roots of the quadratic equation

x^2 + x + (1 - k) = 0,

yielding

\theta, \tau = \frac{-1 \pm \sqrt{4k - 3}}{2}.

The multiplicities of these eigenvalues must be positive integers, which imposes the integrality condition that leads to $4k - 3 being a perfect square (with adjustments for the k=2 case). Solving $4k - 3 = m^2 for odd integers m gives the solutions k=3 (m=3), k=7 (m=5), and k=57 (m=15), alongside the known k=2. Uniqueness for each case follows from exhaustive enumeration and structural arguments in the original analysis.^[28]^[29] Constructions are known and unique for k=2, 3, 7: the cycle graph C_5 for k=2; the Petersen graph for k=3; and the Hoffman-Singleton graph for k=7, which can be constructed as the collinearity graph of a certain block design or via the 5x5 grid with specific edge rules. Each is the unique (k,5)-cage graph satisfying the Moore bound.^[28]^[19] The theorem, published in 1960 by A. J. Hoffman and R. R. Singleton, coined the term "Moore graph" for graphs attaining the Moore bound. It implies that there are at most five Moore graphs of diameter 2 (pending the k=57 case), highlighting the rarity of graphs attaining the Moore bound.^[28]

Krein Parameters and Absolute Bound

In association schemes, including those arising from strongly regular graphs, the Krein parameters q_k^{ij} are defined as the coefficients in the expansion of the Schur (entrywise) product of the primitive idempotents: E_i \circ E_j = \frac{1}{v} \sum_{k=0}^d q_k^{ij} E_k, where v is the number of vertices and d=2 for strongly regular graphs.^[6] These parameters count, in a weighted sense, the number of walks of length 3 connecting vertices in the i-th and j-th eigenspaces, reflecting higher-order intersection properties beyond the standard parameters \lambda and \mu.^[6] For a strongly regular graph with parameters (v, k, \lambda, \mu), the Krein conditions require nonnegativity of certain parameters, equivalent to K_1 \geq 0 and K_2 \geq 0, where \theta > 0 > \tau are the nontrivial eigenvalues, f and g are their multiplicities with f + g = v - 1, K_1 = (k + \theta)(\tau + 1)^2 - (\theta + 1)(k + \theta + 2 \theta \tau), and K_2 = (k + \tau)(\theta + 1)^2 - (\tau + 1)(k + \tau + 2 \theta \tau).^[6] The Krein parameters satisfy orthogonality relations derived from the Bose-Mesner algebra, the commutative algebra generated by the adjacency matrices of the association scheme. Specifically, the dual eigenmatrix Q with entries Q_{ij} obeys \sum_l v_l Q_{li} Q_{lj} = v m_i \delta_{ij}, where v_l and m_i are valencies and multiplicities, respectively; this mirrors the orthogonality of the primal eigenmatrix P and ensures the parameters integrate consistently across eigenspaces.^[6] These relations imply Krein conditions such as K_1 \geq 0 and K_2 \geq 0, which bound the eigenvalues: for instance, the minimal eigenvalue satisfies \tau \geq -1 - \sqrt{k-1}, derived from nonnegativity requirements on the quadratic forms involving the parameters.^[6] Violation of these conditions rules out parameter sets, as seen in nonexistence proofs for proposed strongly regular graphs. The absolute bound refines eigenvalue-based limits on v using Krein parameters. The Krein absolute bound tightens constraints to v \leq \frac{f(f+3)}{2} or v \leq \frac{g(g+3)}{2}, obtained via Neumaier's inequality from the nonnegativity of Krein parameters in the idempotent expansion.^[6] This derivation leverages the spectrum, ensuring the bound holds with equality only for certain tight designs like the Higman-Sims graph.^[6] In applications, the absolute bound strengthens the Hoffman-Singleton theorem by excluding additional parameter sets beyond Moore graphs, such as ruling out (v=50, k=21, \lambda=4, \mu=12) where the multiplicity g=7 of \tau=-9 violates v \leq g(g+3)/2 = 35.^[6] It also aids classification of small strongly regular graphs, confirming existence for all feasible sets up to v=512 except specific cases like the putative 57-vertex graph.^[6] Unlike simpler bounds, the Krein bound incorporates higher-order walk constraints to provide a precise upper limit on v.^[6]

Open Problems

The 57-Regular Moore Graph

The Hoffman-Singleton theorem predicts that a Moore graph of diameter 2 and degree 57, if it exists, must be a strongly regular graph with parameters (3250, 57, 0, 1). These parameters indicate a graph on 3250 vertices where each vertex has degree 57, adjacent vertices share no common neighbors (λ=0), and non-adjacent vertices share exactly one common neighbor (μ=1).^[30] No explicit construction of this graph has been found since the theorem's publication in 1960, despite extensive efforts.^[30] Computer-assisted searches, assuming various constraints on the automorphism group such as subgroups of order up to 10^5, have yielded negative results, ruling out many potential structural forms.^[31] In 2020, Makhnev claimed to prove the non-existence of this graph as a distance-regular graph with the given intersection array {57,56;1,0}.^[32] However, a 2024 analysis by Brouwer identified errors in Makhnev's proof, particularly in the handling of Terwilliger subconstituents, leaving the existence question open as of 2025.^[33] If such a graph exists, it would be unique up to isomorphism, potentially linking to exotic structures like sporadic simple groups or finite geometries due to its highly symmetric parameters.^[30] The parameters satisfy the Krein bounds and absolute bound for strongly regular graphs, confirming feasibility at those levels. Nonetheless, challenges remain in verifying eigenvalue integrality and resolving automorphism group constraints, which continue to obstruct a definitive resolution.^[30]

Conway's 99-Graph Problem

Conway's 99-graph problem concerns the existence of a strongly regular graph with parameters (99, 14, 1, 2), denoted srg(99, 14, 1, 2). In such a graph, there are 99 vertices, each of degree 14, every pair of adjacent vertices shares exactly one common neighbor, and every pair of non-adjacent vertices shares exactly two common neighbors. The parameter λ = 1 implies that each edge lies in a unique triangle, as the single common neighbor completes precisely one such cycle with the edge's endpoints.^[34] The problem originated in the 1970s when John H. Conway posed it as a challenge in combinatorial design, offering a $1,000 prize for its resolution. Conway had been investigating the problem as early as 1975, and it was formally included among five such prize problems he curated. The graph, if it exists, would satisfy the condition that every edge belongs to a unique triangle and every non-edge to a unique quadrilateral, making it a canonical example in extremal graph theory.^[35]^[36] As of 2025, the existence of the srg(99, 14, 1, 2) remains an open question, with no construction or proof of non-existence established. Related smaller cases in the family of strongly regular graphs with λ = 1 and μ = 2 have been resolved negatively; for instance, the putative srg(19, 6, 1, 2) was disproven via a combinatorial argument partitioning the vertex set around a triangle and deriving contradictions in the induced subgraphs. Recent progress includes analyses assuming existence to constrain the automorphism group: if the graph exists, its full automorphism group must have order dividing 2 · 3^3 · 7 · 11, with transitive actions limited to small primes, and the order restricted to forms like 2^a 3^b where a + b ≤ 1. Computational efforts, including brute-force and satisfiability-based searches for consistent subgraphs (such as neighborhoods of adjacent vertices), have yielded negative results, failing to identify viable partial structures up to order 20 or so.^[37]^[38] If the srg(99, 14, 1, 2) exists, it would correspond to a unique 3-(99, 15, 7) balanced incomplete block design, where the blocks are the 15-subsets containing a fixed point's neighborhood plus itself. This connection extends to potential links with finite geometries, as the parameters align with certain incidence structures in projective or affine spaces, though no explicit geometric realization is known.^[39]

References

[1]
Strongly regular graphs, partial geometries and partially balanced ...
R. C. Bose and W. H. Clatworthy, Some classes of partially balanced designs ... The Pacific Journal of Mathematics is published quarterly, in March ...
[2]
Strongly Regular Graph -- from Wolfram MathWorld
A k-regular simple graph G on nu nodes is strongly k-regular if there exist positive integers k, lambda, and mu such that every vertex has k neighbors.
[3]
[PDF] Representations of Directed Strongly Regular Graphs - WPI
Aug 11, 2005 · We say that Γ is a directed strongly regular graph with parameters v, k, t, λ, µ if 0 <t<k, and A satisfies the following matrix equations: JA ...
[4]
Strongly regular graphs - Andries E. Brouwer
A strongly regular graph with parameters (v,k,λ,μ) is a graph with v points (vertices), such that each point has precisely k neighbours.Missing: formal | Show results with:formal
[5]
[PDF] Strongly regular graphs - CWI
Strongly regular graphs are distance-regular graphs of diameter 2, studied in statistics, geometry, group theory, and combinatorics.
[6]
Strongly Regular Graph - an overview | ScienceDirect Topics
Strongly regular graphs are well-studied and are equivalent to symmetric two-class association schemes. Corresponding to any strongly regular graph Γ is a 3 ...
[7]
Classification and Analysis of Partially Balanced Incomplete Block ...
R. C. BOSE AND T. SHIMAMOTO. Univeraity of North Carolina. I. INTRODUCTION. INCOMPLETE block designs are now in fairly general use, especially the balanced ...
[8]
Strongly regular graphs, partial geometries and partially balanced ...
Pacific Journal of Mathematics. ... R. C. Bose "Strongly regular graphs, partial geometries and partially ...
[9]
[2406.09550] New Strongly Regular Graphs Found via Local ... - arXiv
Jun 13, 2024 · In this work, we use local search to find PDSs. We found PDSs with 62 different parameter values in 1254 nonisomorphic groups of orders at most 147.Missing: discoveries 2020-2025
[10]
New Strongly Regular Graphs Found via Local Search for Partial ...
Feb 14, 2025 · In this work, we use local search to find PDSs. We found PDSs with 62 different parameter values in 1254 nonisomorphic groups of orders at most 147.Missing: discoveries 2020-2025
[11]
[PDF] 4.3 Two classes of strongly regular graphs - maths.nuigalway.ie
Families of examples of the second type are a bit harder to construct, although one example is the cycle C5, which has parameters (5, 2, 0, 1). In this graph ...
[12]
Paley Graph -- from Wolfram MathWorld
Paley graphs are self-complementary, strongly regular, conference graphs, and Hamiltonian. All Paley graph are conference graphs (Godsil and Royle 2001, p. 222) ...
[13]
[PDF] The extendability of matchings in strongly regular graphs
Feb 25, 2014 · If k = 4, then G is K4,4,K2,2,2 or the Lattice graph. L2(3) which is the unique (9,4,1,2)-SRG. If G is K4,4 or K2,2,2, the proof is immediate.
[14]
[PDF] Strongly Regular Graphs, part 1 23.1 Introduction 23.2 Definitions
Nov 18, 2009 · It has parameters n = 5, k = 2, λ = 0, µ = 1. 23.4 Lattice Graphs. For a positive integer n, the lattice graph Ln is the graph with vertex set { ...Missing: L2( | Show results with:L2(
[15]
Petersen graph
It is the unique strongly regular graph with parameters v = 10, k = 3, λ = 0, μ = 1, and has spectrum 31 15 (-2)4. The Petersen graph is one of the Moore ...
[16]
[PDF] Distance-regular graphs - The Electronic Journal of Combinatorics
Dec 19, 2014 · (for more on such graphs, see [85, Ch. 9]). The Petersen graph is the same as the Odd graph O3. For an integer k ⩾ 2, the vertices of the Odd ...
[17]
Hoffman-Singleton Graph -- from Wolfram MathWorld
The Hoffman-Singleton graph is a strongly regular graph with parameters (nu,k,lambda,mu)=(50,7,0 . It is an integral graph with graph spectrum (-3)^(21)2 ...
[18]
[PDF] On the Graphs of Hoffman-Singleton and Higman-Sims
The graph G is strongly regular with parameters (100, 22, 0, 6). This implies that G is the Higman-Sims graph, by the uniqueness theorem of Gewirtz [12]. Remark ...
[19]
Sims-Gewirtz graph - Andries E. Brouwer
Up. Sims-Gewirtz graph. There is a unique strongly regular graph with parameters v = 56, k = 10, λ = 0, μ = 2. The spectrum is 101 235 (–4)20.
[20]
https://aeb.win.tue.nl/graphs/Sims-Gewirtz.html
[21]
https://doi.org/10.1002/sapm1933121311
[22]
On a family of strongly regular graphs with λ=1 - ScienceDirect
In this paper, we give a complete description of strongly regular graphs with parameters ( ( n 2 + 3 n − 1 ) 2 , n 2 ( n + 3 ) , 1 , n ( n + 1 ) ) .
[23]
[PDF] On the clique number of a strongly regular graph
May 18, 2018 · Strongly regular graphs whose parameters satisfy k = (v - 1)/2, λ = (v - 5)/4, and. µ = (v - 1)/4 are called type I or conference graphs.
[24]
https://doi.org/10.1007/978-3-642-74265-4
[25]
[PDF] Matrix techniques for strongly regular graphs and related geometries
A graph (simple, undirected and loopless) of order v is strongly regular with parameters v, k, λ, µ whenever it is not complete or edgeless and.Missing: double | Show results with:double<|control11|><|separator|>
[26]
[PDF] New Strongly Regular Graphs from Finite Geometries via Switching
Jul 14, 2019 · and O−(n,3) are not determined by its parameters for n ≥ 6. ... Recall that Γ is a strongly regular graph, so Γ is a strongly regular graph.
[27]
On Linear Associative Algebras Corresponding to ... - Project Euclid
March, 1959 On Linear Associative Algebras Corresponding to Association Schemes of Partially Balanced Designs. R. C. Bose, Dale M. Mesner · DOWNLOAD PDF + ...
[28]
[PDF] On Moore Graphs with Diameters 2 and 3
Theorem 1. No cycle of length less than 5 exists in the graph. If there were such a cycle, designate one of its nodes as the distinguished node. Then equality ...
[29]
[PDF] Very few Moore Graphs - WordPress.com
Abstract. We prove here a well known result in graph theory, originally proved by Hoffman and Singleton, that any non-trivial Moore graph of diameter 2 is ...
[30]
A survey on the missing Moore graph - ScienceDirect.com
May 15, 2019 · This is a survey on some known properties of the possible Moore graph (or graphs) Υ with degree 57 and diameter 2. Moreover, we give some new results about it.
[31]
[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 [205] was devoted to Moore graphs of diameter 2 and 3. In the case ...
[32]
Moore graph with parameters (3250,57,0,1) does not exist - arXiv
The paper proves that a Moore graph with parameters (3250,57,0,1) does not exist, as a distance-regular graph with the given intersection array does not exist.
[33]
[PDF] On the nonexistence of the 3250-point Moore graph
2020-10-28 .. 2024-08-22. Abstract. Makhnev announced the nonexistence of a strongly regular graph with parameters (v, k, λ, µ) = (3250, 57, 0, 1).
[34]
[2409.10620] The Lower Bound for Number of Hexagons in Strongly ...
Sep 16, 2024 · The existence of srg(99,14,1,2) has been a question of interest for several decades to the moment. In this paper we consider the structural ...
[35]
[PDF] Five $1,000 Problems (Update 2017) - John H. Conway - OEIS
Oct 13, 2014 · Problem 2. 99-Graph: Is there a graph with 99 vertices in which every edge (i.e. pair of joined vertices) belongs to a unique triangle and ...Missing: origin | Show results with:origin
[36]
On the automorphism group of a putative Conway 99-graph - arXiv
Aug 6, 2023 · A Conway 99-graph is a strongly regular graph with parameters (99,14,1,2). The paper shows that if divisibility by 2 implies |G| divides 6, ...
[37]
https://www.win.tue.nl/~aeb/graphs/srg/srgtab.html
[38]
https://arxiv.org/abs/2511.06569
[39]
[PDF] On the Strongly Regular Graph of Parameters (99, 14, 1, 2)
Definition 1.1. A strongly regular graph with parameters (n, k, λ, µ) is a k-regular graph on n vertices such that a pair of vertices has λ neighbors in common ...