Strongly regular graph: Difference between revisions

Revision as of 15:35, 9 August 2023

Revision as of 14:37, 9 September 2023

Line 1:

{{Short description|Regular graph where allevery linkedtwo nodedirectly pairsconnected vertices have the same degreenumber of mutual neighbors, as do allevery two unlinkedindirectly nodeconnected pairsvertices.}}

[[Image:Paley13.svg|thumb|upright=1.1|The [[Paley graph]] of order 13, a strongly regular graph with parameters {{math|srg(13,6,2,3)}}.]]

{{Graph families defined by their automorphisms}}

In [[graph theory]], a '''strongly regular graph''' ('''SRG''') is defineda as[[regular follows. Letgraph]] {{math|1=''G'' = (''V'', ''E'')}} be a [[regular graph]] with {{mvar|v}} vertices and [[Degree (graph theory)|degree]] {{mvar|k}}. {{mvar|G}} is said to be '''strongly regular''' if there are also [[integer]]s {{math|λ}} and {{math|μ}} such that:

* Every two [[adjacent vertices]] have {{math|λ}} common neighbours.,

* Every two non-adjacent vertices have {{math|μ}} common neighbours.,

for some integers {{math|\lambda and \mu}}.

The [[complement graph|complement]] of an {{math|srg(''v'', ''k'', λ, μ)}} is also strongly regular. It is a {{math|srg(''v'', ''v'' − ''k'' − 1, ''v'' − 2 − 2''k'' + μ, ''v'' − 2''k'' + λ)}}.

Line 15 ⟶ 17:

A strongly regular graph is denoted 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 (whose 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, refer to the larger eigenvalue as ''r'' (with multiplictymultiplicity ''f'') and the smaller one as ''s'' (with multiplicity ''g'').

==History==