Strongly regular graph: Difference between revisions

Revision as of 22:01, 10 June 2022

Revision as of 20:12, 21 June 2022

Line 1:

{{Short description|Regular graph where all linked node pairs have same degree, as do all unlinked node pairs}}

[[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 defined as follows. Let {{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.

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

A strongly regular graph is a [[distance-regular graph]] with diameter 2 whenever μ is non-zero. It is a [[locally linear graph]] whenever {{nowrapmath|1=λ {{=}} 1}}.

==Etymology==