“Berlekamp–van Lint–Seidel graph”的意思、由来-开放百科全书

In graph theory, the Berlekamp–van Lint–Seidel graph is a locally linear strongly regular graph 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, and {{ill|Johan Jacob Seidel|de}} as the 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 eigenvalues of its adjacency matrix are integers.{{r|mw}} Like the

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 (9,4,1,2).{{r|mm}} Conway's 99-graph problem concerns the existence of another of these graphs, the one with parameters (99,14,1,2).{{r|con}}

See also

References

1. ^{{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}}
2. ^{{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}}
3. ^{{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}}
4. ^{{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

| volume = 14}}
5. ^{{mathworld|title=Berlekamp-van Lint-Seidel Graph|id=Berlekamp-vanLint-SeidelGraph}}