En teoría de grafos , el problema de los 99 grafos de Conway es un problema sin resolver que plantea la pregunta de si existe un grafo no dirigido con 99 vértices , en el que cada dos vértices adyacentes tienen exactamente un vecino común, y en el que cada dos vértices no adyacentes tienen exactamente dos vecinos comunes. De manera equivalente, cada arista debería ser parte de un único triángulo y cada par no adyacente debería ser una de las dos diagonales de un único 4-ciclo. John Horton Conway ofreció un premio de $1000 por su solución. [1]
Si tal grafo existe, necesariamente sería un grafo localmente lineal y un grafo fuertemente regular con parámetros (99,14,1,2). El primer, tercer y cuarto parámetro codifican el enunciado del problema: el grafo debe tener 99 vértices, cada par de vértices adyacentes debe tener 1 vecino común y cada par de vértices no adyacentes debe tener 2 vecinos comunes. El segundo parámetro significa que el grafo es un grafo regular con 14 aristas por vértice. [2]
Si este gráfico existe, no puede tener simetrías que lleven cada vértice a cada otro vértice. [3] Se conocen restricciones adicionales sobre sus posibles grupos de simetrías. [4] [5]
La posibilidad de un grafo con estos parámetros ya fue sugerida en 1969 por Norman L. Biggs , [6] y su existencia fue señalada como un problema abierto por otros antes de Conway. [3] [7] [8] [9] El propio Conway había trabajado en el problema ya en 1975, [7] pero ofreció el premio en 2014 como parte de un conjunto de problemas planteados en la Conferencia DIMACS sobre Desafíos de la Identificación de Secuencias Enteras. Otros problemas en el conjunto incluyen la conjetura de thrackle , el espaciado mínimo de los conjuntos de Danzer y la cuestión de quién gana después del movimiento 16 en el juego sylver coinage . [1]
En términos más generales, sólo hay cinco posibles combinaciones de parámetros para las cuales podría existir un grafo fuertemente regular con cada arista en un único triángulo y cada no arista formando la diagonal de un único cuadrilátero. Sólo se sabe que existen grafos con dos de estas cinco combinaciones. Estos dos grafos son el grafo de Paley de nueve vértices (el grafo del duoprisma 3-3 ) con parámetros (9,4,1,2) y el grafo de Berlekamp–van Lint–Seidel con parámetros (243,22,1,2). Los parámetros para los cuales se desconocen los grafos son: (99,14,1,2), (6273,112,1,2) y (494019,994,1,2). El problema de los 99 grafos describe la más pequeña de estas combinaciones de parámetros para las cuales se desconoce la existencia de un grafo. [4]
