Gráfico fuertemente regular

Concepto en la teoría de grafos

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 ${\displaystyle \lambda ,\mu \geq 0}$

• cada dos vértices adyacentes tienen λ vecinos comunes, y
• cada dos vértices no adyacentes tienen μ vecinos comunes.

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 , v − k − 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

• El ciclo de longitud 5 es un srg(5, 2, 0, 1).
• El gráfico de Petersen es un srg(10, 3, 0, 1).
• El gráfico de Clebsch es un srg(16, 5, 0, 2).
• El gráfico de Shrikhande es un srg(16, 6, 2, 2) que no es un gráfico transitivo de distancia .
• El gráfico de la torre cuadrada de n  ×  n , es decir, el gráfico lineal de un gráfico bipartito completo balanceado K _{n , n} , es una srg( n ² , 2 n  − 2, n  − 2, 2). Los parámetros para n = 4 coinciden con los del gráfico de Shrikhande, pero los dos gráficos no son isomorfos.
• El gráfico lineal de un grafo completo K _n es un . ${\textstyle \operatorname {srg} \left({\binom {n}{2}},2(n-2),n-2,4\right)}$
• Los gráficos de Chang son srg(28, 12, 6, 4), los mismos que el gráfico lineal de K ₈ , pero estos cuatro gráficos no son isomorfos.
• Todo cuadrángulo generalizado de orden (s, t) tiene como gráfico lineal srg((s + 1)(st + 1), s(t + 1), s − 1, t + 1) . Por ejemplo, GQ(2, 4) tiene como gráfico lineal srg(27, 10, 1, 5).
• El gráfico de Schläfli es un srg(27, 16, 10, 8). ^[4]
• El gráfico de Hoffman-Singleton es un srg(50, 7, 0, 1).
• El gráfico de Sims-Gewirtz es un (56, 10, 0, 2).
• El gráfico M22, también conocido como gráfico de Mesner, es un srg(77, 16, 0, 4).
• El gráfico de Brouwer-Haemers es un srg(81, 20, 1, 6).
• El gráfico de Higman-Sims es un srg(100, 22, 0, 6).
• El gráfico local de McLaughlin es un srg(162, 56, 10, 24).
• El gráfico de Cameron es un srg(231, 30, 9, 3).
• El gráfico de Berlekamp-van Lint-Seidel es un srg(243, 22, 1, 2).
• El gráfico de McLaughlin es un srg(275, 112, 30, 56).
• El gráfico de Paley de orden q es un srg( q , ( q  − 1)/2, ( q  − 5)/4, ( q  − 1)/4). El gráfico de Paley más pequeño, con q = 5 , es el de 5 ciclos (arriba).
• Los gráficos arco-transitivos autocomplementarios son fuertemente regulares.

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. ${\displaystyle \mu =1}$ ${\displaystyle \mu =1}$ ${\displaystyle \lambda }$ ${\displaystyle \mu =1}$ ${\displaystyle \lambda }$

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:

${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$

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. ${\displaystyle k-\lambda -1}$ ${\displaystyle k(k-\lambda -1)}$
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 . ${\displaystyle (v-k-1)}$ ${\displaystyle (v-k-1)\mu }$
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:

${\displaystyle AJ=JA=kJ,}$

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:

${\displaystyle A^{2}=kI+\lambda {A}+\mu (J-I-A)}$

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: ${\displaystyle Jx=0}$

${\displaystyle A^{2}=kI+\lambda {A}+\mu (J-I-A)}$

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

${\displaystyle A^{2}x=kIx+\lambda {A}x+\mu (J-I-A)x}$

Llame al valor propio correspondiente p (que no debe confundirse con el parámetro del gráfico) y sustituya , y : ${\displaystyle \lambda }$ ${\displaystyle Ax=px}$ ${\displaystyle Jx=0}$ ${\displaystyle Ix=x}$

${\displaystyle p^{2}x=kx+\lambda px-\mu x-\mu px}$

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

${\displaystyle p^{2}+(\mu -\lambda )p-(k-\mu )=0}$

Esto da los dos valores propios adicionales . Por lo tanto, hay exactamente tres valores propios para una matriz fuertemente regular. ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )\pm {\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]}$

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 :

• El valor propio k tiene multiplicidad 1.
• El valor propio tiene multiplicidad . ${\displaystyle r={\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]}$ ${\displaystyle f={\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$
• El valor propio tiene multiplicidad . ${\displaystyle s={\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]}$ ${\displaystyle g={\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$

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. ${\displaystyle 2k+(v-1)(\lambda -\mu )\neq 0}$

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 ${\displaystyle 2k+(v-1)(\lambda -\mu )=0}$

${\displaystyle \operatorname {srg} \left(v,{\frac {1}{2}}(v-1),{\frac {1}{4}}(v-5),{\frac {1}{4}}(v-1)\right).}$

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 . ${\displaystyle r={\frac {-1+{\sqrt {v}}}{2}}}$ ${\displaystyle s={\frac {-1-{\sqrt {v}}}{2}}}$ ${\displaystyle {\frac {v-1}{2}}}$

Otras propiedades de los valores propios y sus multiplicidades son:

• ${\displaystyle (A-rI)\times (A-sI)=\mu .J}$, por lo tanto ${\displaystyle (k-r).(k-s)=\mu v}$
• ${\displaystyle \lambda -\mu =r+s}$
• ${\displaystyle k-\mu =-r\times s}$
• ${\displaystyle k\geq r}$
• Dado un srg( v , k , λ, μ) con valores propios r y s , su complemento srg( v , v − k − 1, v − 2 − 2 k + μ, v − 2 k + λ) tiene valores propios -1-s y -1-r .
• Las ecuaciones alternativas para las multiplicidades son y ${\displaystyle f={\frac {(s+1)k(k-s)}{\mu (s-r)}}}$ ${\displaystyle g={\frac {(r+1)k(k-r)}{\mu (r-s)}}}$
• La condición del cociente de marco: . Como corolario, si y sólo si en algún orden. ${\displaystyle vk(v-k-1)=fg(r-s)^{2}}$ ${\displaystyle v=(r-s)^{2}}$ ${\displaystyle {f,g}={k,v-k-1}}$
• Condiciones de Kerin: y ${\displaystyle (v-k-1)^{2}(k^{2}+r^{3})\geq (r+1)^{3}k^{2}}$ ${\displaystyle (v-k-1)^{2}(k^{2}+s^{3})\geq (s+1)^{3}k^{2}}$
• Límite absoluto: y . ${\displaystyle v\leq {\frac {f(f+3)}{2}}}$ ${\displaystyle v\leq {\frac {g(g+3)}{2}}}$
• Garra atada: si , entonces o . ${\displaystyle r+1>{\frac {s(s+1)(\mu +1)}{2}}}$ ${\displaystyle \mu =s^{2}}$ ${\displaystyle \mu =s(s+1)}$

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

${\displaystyle M_{\pm }={\frac {1}{2}}\left[(v-1)\pm {\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$

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 ${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$ ${\displaystyle v=k^{2}+1}$

${\displaystyle M_{\pm }={\frac {1}{2}}\left[k^{2}\pm {\frac {2k-k^{2}}{\sqrt {4k-3}}}\right]}$

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. ${\displaystyle {\frac {2k-k^{2}}{\sqrt {4k-3}}}}$ ${\displaystyle 2k-k^{2}}$ ${\displaystyle {\sqrt {4k-3}}}$

Si el numerador es cero, las posibilidades son: ${\displaystyle 2k-k^{2}}$

• k = 0 y v = 1 produce un gráfico trivial con un vértice y sin aristas, y
• k = 2 y v = 5 produce el gráfico de ciclo de 5 vértices , generalmente dibujado como un pentágono regular . ${\displaystyle C_{5}}$

Si el denominador es un entero t , entonces es un cuadrado perfecto , por lo que . Sustituyendo: ${\displaystyle {\sqrt {4k-3}}}$ ${\displaystyle 4k-3}$ ${\displaystyle t^{2}}$ ${\displaystyle k={\frac {t^{2}+3}{4}}}$

${\displaystyle {\begin{aligned}M_{\pm }&={\frac {1}{2}}\left[\left({\frac {t^{2}+3}{4}}\right)^{2}\pm {\frac {{\frac {t^{2}+3}{2}}-\left({\frac {t^{2}+3}{4}}\right)^{2}}{t}}\right]\\32M_{\pm }&=(t^{2}+3)^{2}\pm {\frac {8(t^{2}+3)-(t^{2}+3)^{2}}{t}}\\&=t^{4}+6t^{2}+9\pm {\frac {-t^{4}+2t^{2}+15}{t}}\\&=t^{4}+6t^{2}+9\pm \left(-t^{3}+2t+{\frac {15}{t}}\right)\end{aligned}}}$

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: ${\displaystyle {\frac {15}{t}}}$ ${\displaystyle t\in \{\pm 1,\pm 3,\pm 5,\pm 15\}}$ ${\displaystyle k\in \{1,3,7,57\}}$

• k = 1 y v = 2 produce un gráfico trivial de dos vértices unidos por una arista,
• k = 3 y v = 10 produce el gráfico de Petersen ,
• k = 7 y v = 50 produce el gráfico de Hoffman-Singleton , descubierto por Hoffman y Singleton en el curso de este análisis, y
• k = 57 y v = 3250 predice un famoso gráfico que no ha sido descubierto desde 1960, ni su existencia ha sido refutada. ^[11]

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

• Geometría parcial
• Matriz de adyacencia de Seidel
• Dos gráficos

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. 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 ${\displaystyle \mu =1}$
8. Belousov, IN; Makhnev, AA (2006), "Sobre grafos fuertemente regulares con y sus automorfismos", Doklady Akademii Nauk , 410 (2): 151–155, MR  2455371 ${\displaystyle \mu =1}$
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

• Andries Brouwer y Hendrik van Maldeghem (2022), Gráficos fuertemente regulares . Cambridge: Prensa de la Universidad de Cambridge. ISBN 1316512037 . ISBN 978-1316512036  
• AE Brouwer, AM Cohen y A. Neumaier (1989), Gráficos regulares de distancia . Berlín, Nueva York: Springer-Verlag. ISBN 3-540-50619-5 , ISBN 0-387-50619-5  
• Chris Godsil y Gordon Royle (2004), Teoría de grafos algebraicos . Nueva York: Springer-Verlag. ISBN 0-387-95241-1 

Enlaces externos

• Eric W. Weisstein , artículo de Mathworld con numerosos ejemplos.
• Gordon Royle , Lista de gráficos y familias más grandes.
• Andries E. Brouwer , Parámetros de gráficos fuertemente regulares.
• Brendan McKay , Algunas colecciones de gráficos.
• Ted Spence, Grafos fuertemente regulares con un máximo de 64 vértices.