Gráfico de Berlekamp-Van Lint-Seidel

Dos dibujos del gráfico de Berlekamp–Van Lint–Seidel

En teoría de grafos , el grafo de Berlekamp–Van Lint–Seidel es un grafo localmente lineal fuertemente regular con parámetros . Esto significa que tiene 243 vértices, 22 aristas por vértice (para un total de 2673 aristas), exactamente un vecino compartido por par de vértices adyacentes y exactamente dos vecinos compartidos por par de vértices no adyacentes. Fue construido por Elwyn Berlekamp , ​​JH van Lint y Johan Jacob Seidel  [de] como el grafo de coset del código ternario de Golay . ^[1] ${\displaystyle (243,22,1,2)}$

Este gráfico es el gráfico de Cayley de un grupo abeliano . Entre los gráficos de Cayley abelianos que son fuertemente regulares y tienen los dos últimos parámetros que difieren en uno, es el único gráfico que no es un gráfico de Paley . ^[2] También es un gráfico integral , lo que significa que los valores propios de su matriz de adyacencia son números enteros. ^[3] Al igual que el gráfico de Sudoku, es un gráfico de Cayley abeliano integral cuyos elementos del grupo tienen todos orden 3, una de las pocas posibilidades para los órdenes en dicho gráfico. ^[4] ${\displaystyle 9\times 9}$

Existen cinco posibles combinaciones de parámetros para grafos fuertemente regulares que tienen un vecino compartido por par de vértices adyacentes y exactamente dos vecinos compartidos por par de vértices no adyacentes. De estos, se sabe que existen dos: el grafo de Berlekamp–Van Lint–Seidel y el grafo de Paley de 9 vértices con parámetros . ^[5] El problema de los 99 grafos de Conway se refiere a la existencia de otro de estos grafos, el de parámetros . ^[6] ${\displaystyle (9,4,1,2)}$ ${\displaystyle (99,14,1,2)}$

Véase también

• Gráfico de juegos

Referencias

1. Berlekamp, ​​ER ; Van Lint, JH ; Seidel, JJ (1973), "Un gráfico fuertemente regular derivado del código ternario perfecto de Golay" (PDF) , A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) , Ámsterdam: North-Holland: 25–30, doi :10.1016/B978-0-7204-2262-7.50008-9, ISBN 9780720422627, Sr.  0364015
2. Arasu, KT; Jungnickel, D .; Ma, SL; Pott, A. (1994), "Gráficos de Cayley fuertemente regulares con ", Journal of Combinatorial Theory , Serie A, 67 (1): 116–125, doi :10.1016/0097-3165(94)90007-8, MR  1280602 ${\displaystyle \lambda -\mu =-1}$
3. Weisstein, Eric W. , "Gráfico de Berlekamp-Van Lint-Seidel", MathWorld
4. Klotz, Walter; Sander, Torsten (2010), "Gráficos integrales de Cayley sobre grupos abelianos", Electronic Journal of Combinatorics , 17 (1): Documento de investigación 81, 13pp, doi : 10.37236/353 , MR  2651734
5. Makhnev, AA; Minakova, IM (enero de 2004), "Sobre automorfismos de grafos fuertemente regulares con parámetros " , Matemáticas discretas y aplicaciones , 14 (2), doi : 10.1515/156939204872374, MR  2069991, S2CID  118034273 ${\displaystyle \lambda =1}$ ${\displaystyle \mu =2}$
6. Conway, John H. , Cinco problemas de 1000 dólares (actualización de 2017) (PDF) , Enciclopedia en línea de secuencias de números enteros , consultado el 12 de febrero de 2019