Gráfico de conferencia

Problema sin resolver en matemáticas

¿Existe un grafo de conferencia para cada número de vértices?

v>1

dónde

v\equiv 1{\bmod {4}}

y

v

¿Es una suma impar de dos cuadrados?

Más problemas sin resolver en matemáticas

En el ámbito matemático de la teoría de grafos , un grafo de conferencia es un grafo fuertemente regular con parámetros v , k = ( v − 1)/2, λ = ( v − 5)/4 y μ = ( v − 1)/4. Es el grafo asociado a una matriz de conferencia simétrica y, por consiguiente, su orden v debe ser 1 ( módulo 4) y suma de dos cuadrados . ^{[ 1 ]}

Se sabe que existen grafos de conferencia para todos los valores pequeños de v permitidos por las restricciones, por ejemplo, v = 5, 9, 13, 17, 25, 29, y (los grafos de Paley ) para todas las potencias primas congruentes con 1 (módulo 4). Sin embargo, hay muchos valores de v permitidos para los que se desconoce la existencia de un grafo de conferencia. El valor más pequeño de v que no tiene un grafo de Paley pero sí un grafo de conferencia es v = 45, encontrado en 1978. ^{[ 2 ]} El siguiente más pequeño, v = 65, se encontró más de cuatro décadas después, en 2021. ^{[ 3 ]}^{[ 4 ]} Hasta ahora, el caso abierto más pequeño es v = 85. ^{[ 4 ]}

Los valores propios de un grafo de conferencia no tienen por qué ser enteros, a diferencia de los de otros grafos fuertemente regulares. Si el grafo es conexo, los valores propios son k con multiplicidad 1 y otros dos valores propios,

{\frac {-1\pm {\sqrt {v}}}{2}},

cada uno con multiplicidad ( v − 1)/2.

El complemento de un grafo de conferencia es siempre un grafo de conferencia con los mismos parámetros, y en muchos casos es autocomplementario, como ocurre con todos los grafos de Paley.

Referencias

^ Brouwer, AE; Cohen, AM; Neumaier, A. (1989). Gráficos regulares de distancia (PDF) . Berlín, Nueva York: Springer-Verlag. ISBN 978-3-540-50619-5.
↑ Mathon, Rudolf (1978). "Matrices de conferencia simétricas de orden pq² + 1" . Revista canadiense de matemáticas . 30 (2): 321– 331. doi : 10.4153/CJM-1978-029-1 .
↑ Gritsenko, Oleg (2021). "Sobre un grafo fuertemente regular con parámetros (65; 32; 15; 16)". arXiv : 2102.05432 [ math.CO ].
1 2 Brouwer, Andries E.; Van Maldeghem, Hendrik (2022). "8.2 Matrices de conferencia y grafos de conferencia". Grafos fuertemente regulares (PDF) . Nuevas monografías matemáticas. Vol. 41. Sociedad Matemática Americana. págs. 189–190 . ISBN 978-1-316-51203-6.