stringtranslate.com

Gráfico fuertemente regular

El gráfico de Paley de orden 13, un gráfico fuertemente regular con parámetros (13,6,2,3) .

En teoría de grafos , un grafo fuertemente regular ( SRG ) es un grafo regular G = ( V , E ) con vértices y grado k tal que para algunos enteros dados

Un gráfico fuertemente regular de este tipo se denota por srg( v , k , λ, μ) ; sus "parámetros" son los números en ( v , k , λ, μ). Su gráfico complementario también es fuertemente regular: es un srg( v , vk − 1, v − 2 − 2 k + μ, v − 2 k + λ) .

Un grafo fuertemente regular es un grafo regular en función de la distancia con un diámetro de 2 siempre que μ no sea cero. Es un grafo localmente lineal siempre que λ = 1 .

Etimología

En la literatura, un grafo fuertemente regular se denota como srg( v , k , λ, μ). Por convención, los grafos que satisfacen la definición de manera trivial se excluyen de los estudios detallados y las listas de grafos fuertemente regulares. Estos incluyen la unión disjunta de uno o más grafos completos de igual tamaño , [1] [2] y sus complementos , los grafos multipartitos completos con conjuntos independientes de igual tamaño.

Andries Brouwer y Hendrik van Maldeghem (ver #Referencias) usan una definición alternativa pero completamente equivalente de un grafo fuertemente regular basada en la teoría de grafos espectrales : un grafo fuertemente regular es un grafo regular finito que tiene exactamente tres valores propios, de los cuales solo uno es igual al grado k , de multiplicidad 1. Esto descarta automáticamente los grafos completamente conectados (que tienen solo dos valores propios distintos, no tres) y los grafos desconectados (para los cuales la multiplicidad del grado k es igual al número de componentes conectados diferentes, que por lo tanto excederían uno). Gran parte de la literatura, incluido Brouwer, se refiere al valor propio más grande como r (con multiplicidad f ) y al más pequeño como s (con multiplicidad g ).

Historia

Los gráficos fuertemente regulares fueron introducidos por RC Bose en 1963. [3] Se basaron en trabajos anteriores de la década de 1950 en el entonces nuevo campo de la teoría de gráficos espectrales .

Ejemplos

Un grafo fuertemente regular se denomina primitivo si tanto el grafo como su complemento son conexos. Todos los grafos anteriores son primitivos, ya que de lo contrario μ = 0 o λ = k .

El problema de los 99 grafos de Conway pide la construcción de un srg(99, 14, 1, 2). Se desconoce si existe un grafo con estos parámetros, y John Horton Conway ofreció un premio de 1000 dólares por la solución de este problema. [5]

Gráficos sin triángulos

Los grafos fuertemente regulares con λ = 0 no tienen triángulos . Aparte de los grafos completos con menos de 3 vértices y todos los grafos bipartitos completos, los siete enumerados anteriormente (pentágono, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22 y Higman-Sims) son los únicos conocidos.

Gráficas geodésicas

Todo grafo fuertemente regular con es un grafo geodésico , un grafo en el que cada dos vértices tienen un camino más corto no ponderado único . [6] Los únicos grafos fuertemente regulares conocidos con son aquellos donde es 0, por lo tanto también libres de triángulos. Estos se denominan grafos de Moore y se exploran a continuación con más detalle. Todavía no se han descartado otras combinaciones de parámetros como (400, 21, 2, 1). A pesar de la investigación en curso sobre las propiedades que tendría un grafo fuertemente regular con, [7] [8] no se sabe si existen más o incluso si su número es finito. [6] Solo se conoce el resultado elemental, que no puede ser 1 para un grafo de este tipo.

Propiedades algebraicas de grafos fuertemente regulares

Relación básica entre parámetros

Los cuatro parámetros de una función srg( v , k , λ, μ) no son independientes. Deben obedecer a la siguiente relación:

La relación anterior se deriva a través de un argumento de conteo como sigue:

  1. Imaginemos que los vértices del grafo se encuentran en tres niveles. Elijamos cualquier vértice como raíz, en el nivel 0. Entonces sus k vecinos se encuentran en el nivel 1 y todos los demás vértices se encuentran en el nivel 2.
  2. Los vértices del Nivel 1 están conectados directamente a la raíz, por lo tanto, deben tener λ otros vecinos en común con la raíz, y estos vecinos comunes también deben estar en el Nivel 1. Dado que cada vértice tiene grado k , quedan aristas para que cada nodo del Nivel 1 se conecte a los vértices del Nivel 2. Por lo tanto, hay aristas entre el Nivel 1 y el Nivel 2.
  3. Los vértices en el Nivel 2 no están conectados directamente a la raíz, por lo tanto, deben tener μ vecinos comunes con la raíz, y estos vecinos comunes deben estar todos en el Nivel 1. Hay vértices en el Nivel 2, y cada uno está conectado a μ vértices en el Nivel 1. Por lo tanto, el número de aristas entre el Nivel 1 y el Nivel 2 es .
  4. Igualando las dos expresiones para los bordes entre el Nivel 1 y el Nivel 2, se obtiene la siguiente relación.

Ecuaciones de matriz de adyacencia

Sea I la matriz identidad y J la matriz de unos , ambas matrices de orden v . La matriz de adyacencia A de un grafo fuertemente regular satisface dos ecuaciones.

Primero:

lo cual es una reformulación del requisito de regularidad. Esto demuestra que k es un valor propio de la matriz de adyacencia con el vector propio de todos los unos.

Segundo:

que expresa una fuerte regularidad. El elemento ij -ésimo del lado izquierdo da el número de caminos de dos pasos de i a j . El primer término del lado derecho da el número de caminos de dos pasos de i de vuelta a i , es decir, k aristas de entrada y salida. El segundo término da el número de caminos de dos pasos cuando i y j están directamente conectados. El tercer término da el valor correspondiente cuando i y j no están conectados. Dado que los tres casos son mutuamente excluyentes y colectivamente exhaustivos , se sigue la simple igualdad aditiva.

Por el contrario, un grafo cuya matriz de adyacencia satisface ambas condiciones anteriores y que no es un grafo completo o nulo es un grafo fuertemente regular. [9]

Valores propios y espectro gráfico

Como la matriz de adyacencia A es simétrica, se deduce que sus vectores propios son ortogonales . Ya hemos observado un vector propio que está formado únicamente por unos, correspondiente al valor propio k . Por lo tanto, los demás vectores propios x deben satisfacer todos donde J es la matriz de todos unos como antes. Tomemos la ecuación establecida previamente:

y multiplica la ecuación anterior por el vector propio x :

Llame al valor propio correspondiente p (que no debe confundirse con el parámetro del gráfico) y sustituya , y :

Elimina x y reorganiza para obtener una ecuación cuadrática:

Esto da los dos valores propios adicionales . Por lo tanto, hay exactamente tres valores propios para una matriz fuertemente regular.

Por el contrario, un gráfico regular conexo con sólo tres valores propios es fuertemente regular. [10]

Siguiendo la terminología de gran parte de la literatura sobre gráficos fuertemente regulares, el valor propio mayor se denomina r con multiplicidad f y el menor se denomina s con multiplicidad g .

Dado que la suma de todos los valores propios es la traza de la matriz de adyacencia , que en este caso es cero, se pueden calcular las respectivas multiplicidades f y g :

Como las multiplicidades deben ser números enteros, sus expresiones proporcionan restricciones adicionales sobre los valores de v , k , μ y λ .

Grafos fuertemente regulares que tienen valores propios enteros con multiplicidades desiguales.

Los grafos fuertemente regulares se denominan grafos de conferencia debido a su conexión con matrices de conferencia simétricas . Sus parámetros se reducen a

Sus valores propios son y , cuyas multiplicidades son iguales a . Además, en este caso, v debe ser igual a la suma de dos cuadrados, relacionado con el teorema de Bruck-Ryser-Chowla .

Otras propiedades de los valores propios y sus multiplicidades son:

Si se violan las condiciones anteriores para cualquier conjunto de parámetros, entonces no existe un gráfico fuertemente regular para esos parámetros. Brouwer ha compilado aquí dichas listas de existencia o no existencia con razones para la no existencia, si las hubiera.

El teorema de Hoffman-Singleton

Como se señaló anteriormente, las multiplicidades de los valores propios se dan por

que deben ser números enteros.

En 1960, Alan Hoffman y Robert Singleton examinaron esas expresiones cuando se aplicaron a los grafos de Moore que tienen λ = 0 y μ = 1. Dichos grafos están libres de triángulos (de lo contrario, λ excedería cero) y cuadriláteros (de lo contrario , μ excedería 1), por lo tanto, tienen una circunferencia (longitud de ciclo más pequeña) de 5. Sustituyendo los valores de λ y μ en la ecuación , se puede ver que , y las multiplicidades de valores propios se reducen a

Para que las multiplicidades sean números enteros, la cantidad debe ser racional, por lo tanto, o bien el numerador es cero o bien el denominador es un número entero.

Si el numerador es cero, las posibilidades son:

Si el denominador es un entero t , entonces es un cuadrado perfecto , por lo que . Sustituyendo:

Como ambos lados son números enteros, debe ser un número entero, por lo tanto t es un factor de 15, es decir , por lo tanto . A su vez:

El teorema de Hoffman-Singleton establece que no existen grafos de Moore de circunferencia 5 fuertemente regulares excepto los enumerados anteriormente.

Véase también

Notas

  1. ^ Brouwer, Andries E; Haemers, Willem H. Espectros de grafos. p. 101 Archivado el 16 de marzo de 2012 en Wayback Machine.
  2. ^ Godsil, Chris; Royle, Gordon. Teoría de grafos algebraicos . Springer-Verlag Nueva York, 2001, pág. 218.
  3. ^ https://projecteuclid.org/euclid.pjm/1103035734, RC Bose, Gráficos fuertemente regulares, geometrías parciales y diseños parcialmente balanceados, Pacific J. Math 13 (1963) 389–419. (p. 122)
  4. ^ Weisstein, Eric W. , "Gráfico de Schläfli", MathWorld
  5. ^ 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
  6. ^ ab Blokhuis, A .; Brouwer, AE (1988), "Gráficos geodésicos de diámetro dos", Geometriae Dedicata , 25 (1–3): 527–533, doi :10.1007/BF00191941, MR  0925851, S2CID  189890651
  7. ^ Deutsch, J.; Fisher, PH (2001), "Sobre gráficos fuertemente regulares con ", European Journal of Combinatorics , 22 (3): 303–306, doi : 10.1006/eujc.2000.0472 , MR  1822718
  8. ^ Belousov, IN; Makhnev, AA (2006), "Sobre grafos fuertemente regulares con y sus automorfismos", Doklady Akademii Nauk , 410 (2): 151–155, MR  2455371
  9. ^ Cameron, PJ; van Lint, JH (1991), Diseños, gráficos, códigos y sus vínculos, London Mathematical Society Student Texts 22, Cambridge University Press, pág. 37, ISBN 978-0-521-42385-4
  10. ^ Godsil, Chris; Royle, Gordon. Teoría de grafos algebraicos . Springer-Verlag, Nueva York, 2001, Lema 10.2.1.
  11. ^ Dalfó, C. (2019), "Una encuesta sobre el grafo de Moore que falta", Álgebra lineal y sus aplicaciones , 569 : 1–14, doi :10.1016/j.laa.2018.12.035, hdl : 2117/127212 , MR  3901732, S2CID  126689579

Referencias

Enlaces externos