View source for Berlekamp–Van Lint–Seidel graph

[[File:The Berlekamp-van Lint-Seidel Graph.png|thumb|460x460px|Two drawings of the Berlekamp–Van Lint–Seidel graph]]
In [[graph theory]], the '''Berlekamp–Van Lint–Seidel graph''' is a [[locally linear graph|locally linear]] [[strongly regular graph]] with parameters <math>(243,22,1,2)</math>. This means that it has 243 vertices, 22 edges per vertex (for a total of 2673 edges), exactly one shared neighbor per pair of adjacent vertices, and exactly two shared neighbors per pair of non-adjacent vertices. It was constructed by [[Elwyn Berlekamp]], [[J. H. van Lint]], and {{ill|Johan Jacob Seidel|de}} as the [[Schreier coset graph|coset graph]] of the [[ternary Golay code]].{{r|bvls}}

This graph is the [[Cayley graph]] of an [[abelian group]]. Among abelian Cayley graphs that are strongly regular and have the last two parameters differing by one, it is the only graph that is not a [[Paley graph]].{{r|ajmp}} It is also an [[integral graph]], meaning that the [[eigenvalue]]s of its [[adjacency matrix]] are integers.{{r|mw}} Like the <math>9\times 9</math> [[Sudoku graph]] it is an integral abelian Cayley graph whose group elements all have order 3, one of a small number of possibilities for the orders in such a graph.{{r|ks}}

There are five possible combinations of parameters for strongly regular graphs that have one shared neighbor per pair of adjacent vertices and exactly two shared neighbors per pair of non-adjacent vertices. Of these, two are known to exist: the Berlekamp–Van Lint–Seidel graph and the 9-vertex Paley graph with parameters <math>(9,4,1,2)</math>.{{r|mm}} [[Conway's 99-graph problem]] concerns the existence of another of these graphs, the one with parameters <math>(99,14,1,2)</math>.{{r|con}}

==See also==
*[[Games graph]]

==References==
{{reflist|refs=

<ref name=ajmp>{{citation
 | last1 = Arasu | first1 = K. T.
 | last2 = Jungnickel | first2 = D. | author2-link = Dieter Jungnickel 
 | last3 = Ma | first3 = S. L.
 | last4 = Pott | first4 = A.
 | doi = 10.1016/0097-3165(94)90007-8
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 1280602
 | pages = 116–125
 | series = Series A
 | title = Strongly regular Cayley graphs with <math>\lambda-\mu=-1</math>
 | volume = 67
 | year = 1994| doi-access = 
 }}</ref>

<ref name=con>{{citation
 | last = Conway | first = John H. | author-link = John Horton Conway
 | accessdate = 2019-02-12
 | publisher = Online Encyclopedia of Integer Sequences
 | title = Five $1,000 Problems (Update 2017)
 | url = https://oeis.org/A248380/a248380.pdf}}</ref>

<ref name=bvls>{{citation
 | last1 = Berlekamp | first1 = E. R. | author1-link = Elwyn Berlekamp
 | last2 = Van Lint | first2 = J. H. | author2-link = J. H. van Lint
 | last3 = Seidel | first3 = J. J.
 | doi = 10.1016/B978-0-7204-2262-7.50008-9
 | journal = A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971)
 | mr = 0364015
 | pages = 25–30
 | publisher = North-Holland | location = Amsterdam
 | title = A strongly regular graph derived from the perfect ternary Golay code
 | year = 1973| isbn = 9780720422627 | url = https://pure.tue.nl/ws/files/2157517/593575.pdf
 }}</ref>

<ref name=ks>{{citation
 | last1 = Klotz | first1 = Walter
 | last2 = Sander | first2 = Torsten
 | issue = 1
 | journal = Electronic Journal of Combinatorics
 | mr = 2651734
 | page = Research Paper 81, 13pp
 | title = Integral Cayley graphs over abelian groups
 | url = https://www.combinatorics.org/Volume_17/Abstracts/v17i1r81.html
 | volume = 17
 | year = 2010| doi = 10.37236/353
 | doi-access = free
 }}</ref>

<ref name=mm>{{citation
 | last1 = Makhnev | first1 = A. A.
 | last2 = Minakova | first2 = I. M.
 | date = January 2004
 | doi = 10.1515/156939204872374
 | issue = 2
 | journal = Discrete Mathematics and Applications
 | mr = 2069991
 | title = On automorphisms of strongly regular graphs with parameters <math>\lambda=1</math>, <math>\mu=2</math>
 | volume = 14| s2cid = 118034273
 }}</ref>

<ref name=mw>{{mathworld|title=Berlekamp–Van Lint-Seidel Graph|id=Berlekamp-vanLint-SeidelGraph|mode=cs2}}</ref>

}}

[[Category:Individual graphs]]
[[Category:Strongly regular graphs]]
{{DEFAULTSORT:Berlekamp-Van Lint-Seidel graph}}