graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Berlekamp–Van Lint–Seidel graph is a locally linear

strongly regular graph In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that: * Every two adjacent vertices have comm ...

with parameters

(243,22,1,2)

. 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 Jacobus Hendricus ("Jack") van Lint (1 September 1932 – 28 September 2004) was a Dutch mathematician, professor at the Eindhoven University of Technology, of which he was rector magnificus from 1991 till 1996. He gained his Ph.D. from Utrecht ...

, and as the coset graph of the

ternary Golay code In coding theory, the ternary Golay codes are two closely related error-correcting codes. The code generally known simply as the ternary Golay code is an 1, 6, 53-code, that is, it is a linear code over a ternary alphabet; the relative distance ...

. This graph is the

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Ca ...

of an

abelian group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is com ...

. 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 In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, ...

. It is also an integral graph, meaning that the

eigenvalue In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denot ...

s of its

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...

are integers. Like the

9\times 9

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. 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

(9,4,1,2)

. Conway's 99-graph problem concerns the existence of another of these graphs, the one with parameters

(99,14,1,2)

References

{{reflist, refs= {{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 The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, mr = 1280602 , pages = 116–125 , series = Series A , title = Strongly regular Cayley graphs with

\lambda-\mu=-1

, volume = 67 , year = 1994, doi-access = free {{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 {{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, url = https://pure.tue.nl/ws/files/2157517/593575.pdf {{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 {{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

\lambda=1

\mu=2

, volume = 14 {{mathworld, title=Berlekamp–Van Lint-Seidel Graph, id=Berlekamp-vanLint-SeidelGraph, mode=cs2 Individual graphs Strongly regular graphs

See also

References