Conde de Berlekamp-van Lint-Seidel

El grafo de Berlekamp-van Lint-Seidel es un grafo fuertemente regular localmente lineal con parámetros (243,22,1,2), lo que significa que el grafo tiene 243 vértices, 22 aristas por vértice (para un total de 2673 aristas), exactamente uno un vértice común para cada par de vértices adyacentes, y exactamente dos vértices comunes para cualquier par de vértices no adyacentes. El grafo fue construido por Alvin Berlekamp , ​​J. G. van Lint y Johan Jakob Seidel como un grafo de adyacencia de códigos ternarios de Golay [1] .

Propiedades

El gráfico es el gráfico de Cayley del grupo abeliano . Entre los gráficos abelianos de Cayley que son estrictamente regulares y en los que los dos últimos parámetros difieren en uno, este es el único gráfico que no es igual al gráfico de Paley [2] . También es un grafo de enteros , lo que significa que los valores propios de su matriz de adyacencia son enteros [3] . Al igual que un gráfico de Sudoku , es un gráfico completo de Abelian Cayley, cuyos elementos de grupo tienen orden 3, uno de los números más pequeños posibles para los órdenes en tales gráficos [4] .

Otros gráficos de este tipo

Hay cinco combinaciones posibles de parámetros para gráficos fuertemente regulares que tienen un vértice común para cada par de vértices adyacentes y exactamente dos vecinos comunes para vértices no adyacentes. De estos, se conoce la existencia de dos gráficos: este es el gráfico de Berlekamp-van Lint-Seidel y el gráfico de Paley con 9 vértices con parámetros (9,4,1,2) [5] . El problema de 99 gráficos de Conway pregunta sobre la existencia de otro gráfico de este tipo con parámetros (99,14,1,2) [6] .

Véase también

Notas

  1. ↑ Berlekamp ER, van Lint JH, Seidel JJ Un gráfico fuertemente regular derivado del código Golay ternario perfecto // Un estudio de la teoría combinatoria (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). - Holanda Septentrional, 1973. - S. 25-30 . -doi : 10.1016/ B978-0-7204-2262-7.50008-9 .
  2. ↑ Arasu KT, Jungnickel D., Ma SL, Pott A. Gráficos de Cayley fuertemente regulares con  // Journal of Combinatorial Theory . - 1994. - T. 67 , núm. 1 . — S. 116–125 . - doi : 10.1016/0097-3165(94)90007-8 .
  3. ↑ Weisstein, Eric W. Berlekamp-van Lint-Seidel Gráfico  en el sitio web Wolfram MathWorld .
  4. ↑ Walter Klotz, Torsten Sander. Gráficos integrales de Cayley sobre grupos abelianos  // Electronic Journal of Combinatorics. - 2010. - T. 17 , núm. 1 . — C. Documento de investigación 81, 13 págs .
  5. ↑ Makhnev AA, Minakova IM,. Sobre automorfismos de grafos fuertemente regulares con parámetros ,  // Matemáticas Discretas y Aplicaciones. - 2004. - enero ( vol. 14 , número 2 ). -doi : 10.1515/ 156939204872374 .
  6. ↑ John H. Conway. Cinco problemas de $1,000 (Actualización 2017) . — Enciclopedia en línea de secuencias enteras.