Content deleted Content added
m →Important topics: Added association schemes |
m →Important topics: Added strongly regular graphs |
||
Line 18:
An [[association scheme]] is a collection of [[binary relation]]s satisfying certain compatibility conditions. Association schemes provide a unified approach to many topics, for example [[combinatorial design]]s and [[coding theory]].<ref>{{harvnb|Bannai|Ito|1984}}</ref><ref>{{harvnb|Godsil|1993}}</ref> In algebra, association schemes generalize [[group (mathematics)|group]]s, and the theory of association schemes generalizes the [[group character|character theory]] of [[group representation|linear representations]] of groups.<ref>{{harvnb|Bailey|2004|loc=pg. 387}}</ref><ref>{{harvnb|Zieschang|2005b}}</ref><ref>{{harvnb|Zieschang|2005a}}</ref>
===Strongly regular graphs===
{{main|Strongly regular graph}}
A [[strongly regular graph]] is defined as follows. Let ''G'' = (''V'',''E'') be a [[regular graph]] with ''v'' vertices and degree ''k''. ''G'' is said to be '''strongly regular''' if there are also [[integer]]s λ and μ such that:
* Every two [[adjacent vertices]] have λ common neighbours.
* Every two non-adjacent vertices have μ common neighbours.
A graph of this kind is sometimes said to be an srg(''v'', ''k'', λ, μ).
Some authors exclude graphs which satisfy the definition trivially, namely those graphs which are 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]</ref><ref>Godsil, Chris; Royle, Gordon. ''Algebraic Graph Theory''. Springer-Verlag New York, 2001, p. 218.</ref> and their [[complement graph|complements]], the [[Turán graph]]s.
== See also ==
| |||