Strongly regular graph: Difference between revisions

Revision as of 09:58, 5 October 2023

Revision as of 09:27, 21 January 2024

Line 12:

==Etymology==

A strongly regular graph is denoted as an srg(''v'', ''k'', λ, μ) in the literature. By convention, graphs which satisfy the definition trivially are excluded from detailed studies and lists of strongly regular graphs. These include the disjoint union of one or more equal-sized [[complete graph]]s,<ref>[http://homepages.cwi.nl/~aeb/math/ipm.pdf Brouwer, Andries E; Haemers, Willem H. ''Spectra of Graphs''. p. 101] {{Webarchive|url=https://web.archive.org/web/20120316102909/http://homepages.cwi.nl/~aeb/math/ipm.pdf |date=2012-03-16 }}</ref><ref>Godsil, Chris; Royle, Gordon. ''Algebraic Graph Theory''. Springer-Verlag New York, 2001, p. 218.</ref> and their [[complement graph|complements]], the complete [[multipartite graph]]s with equal-sized independent sets.

[[Andries Brouwer]] and Hendrik van Maldeghem (see [[#References]]) use an alternate but fully equivalent definition of a strongly regular graph based on [[spectral graph theory]]: a strongly regular graph is a finite regular graph that has exactly three eigenvalues, only one of which is equal to the degree ''k'', of multiplicity 1. This automatically rules out fully connected graphs (which have only two distinct eigenvalues, not three) and disconnected graphs (whosefor which the multiplicity of the degree ''k'' is equal to the number of different connected components, which would therefore exceed one). Much of the literature, including Brouwer, referrefers to the larger eigenvalue as ''r'' (with multiplicity ''f'') and the smaller one as ''s'' (with multiplicity ''g'').

==History==