Gráfico muy regular

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

Familias de gráficos definidas por sus automorfismos
distancia-transitiva	→	distancia regular	←	muy regular
↓
simétrico (arco-transitivo)	←	t -transitivo, t  ≥ 2		simétrico sesgado
↓
(si está conectado) vértice y borde transitivo	→	edge-transititive y regular	→	borde transitivo
↓		↓		↓
vértice-transitivo	→	regular	→	(si es bipartito) birregular
↑
Gráfico de Cayley	←	simétrico cero		asimétrico

En teoría de grafos , un grafo fuertemente regular se define como sigue. Sea G = ( V , E ) una gráfica regular con v vértices y grado k . Se dice que G es fuertemente regular si también hay números enteros λ y μ tales que:

• Cada dos vértices adyacentes tienen λ vecinos comunes.
• Cada dos vértices no adyacentes tienen μ vecinos comunes.

A veces se dice que un gráfico de este tipo es un srg ( v , k , λ, μ). Raj Chandra Bose introdujo gráficos muy regulares en 1963. ^[1]

Algunos autores excluyen los gráficos que satisfacen la definición de manera trivial, a saber, aquellos gráficos que son la unión disjunta de uno o más gráficos completos de igual tamaño , ^{[2] [3]} y sus complementos , los gráficos multipartitos completos con conjuntos independientes de igual tamaño.

El complemento de un srg ( v , k , λ, μ) también es muy regular. Es un srg ( v , v − k −1, v −2−2 k + μ, v −2 k + λ).

Un gráfico fuertemente regular es un gráfico de distancia regular con diámetro 2 siempre que μ sea distinto de cero. Es un gráfico localmente lineal siempre que λ = 1.

Propiedades

Relación entre parámetros

Los cuatro parámetros en un srg ( v , k , λ, μ) no son independientes y deben obedecer la siguiente relación:

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

La relación anterior se puede derivar muy fácilmente a través de un argumento de conteo de la siguiente manera:

1. Imagina que los vértices del gráfico se encuentran en tres niveles. Elija cualquier vértice como raíz, en el nivel 0. Luego, 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 en el 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 cada Nivel 1 nodo para conectarse a los nodos en el Nivel 2. Por lo tanto, hay bordes entre el Nivel 1 y el Nivel 2.${\displaystyle k-\lambda -1}$${\displaystyle k\times (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 μ nodos 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)\times \mu }$
4. Al igualar las dos expresiones para los bordes entre el Nivel 1 y el Nivel 2, sigue la relación.

Matriz de adyacencia

Let Me denotar la matriz identidad y dejar J denota la matriz de los , ambas matrices de orden v . La matriz de adyacencia A de un gráfico fuertemente regular satisface dos ecuaciones. Primero:

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

que es una reafirmación trivial del requisito de regularidad. Esto muestra que k es un valor propio de la matriz de adyacencia con el vector propio de todos unos. La segunda es una ecuación cuadrática,

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

que expresa una fuerte regularidad. El elemento ij -ésimo del lado izquierdo da el número de trayectorias de dos pasos desde i hasta j . El primer término del RHS da el número de auto-trayectos desde i hasta i , es decir, k bordes hacia afuera y hacia adentro. El segundo término da el número de caminos de dos pasos cuando i y j están conectados directamente. 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 gráfico cuya matriz de adyacencia satisface las dos condiciones anteriores y que no es un gráfico completo o nulo es un gráfico muy regular. ^[4]

Autovalores

La matriz de adyacencia del gráfico tiene exactamente tres valores propios :

• k , cuya multiplicidad es 1 (como se ve arriba)
• ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right],}$ cuya multiplicidad es ${\displaystyle {\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$
• ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right],}$ cuya multiplicidad es ${\displaystyle {\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 λ , relacionados con las llamadas condiciones de Kerin .

Gráficos muy regulares a los que se les llama gráficos 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 {\text{srg}}\left(v,{\tfrac {1}{2}}(v-1),{\tfrac {1}{4}}(v-5),{\tfrac {1}{4}}(v-1)\right).}$

Gráficos muy regulares para los que tienen valores propios enteros con multiplicidades desiguales.${\displaystyle 2k+(v-1)(\lambda -\mu )\neq 0}$

Por el contrario, un gráfico regular conectado con solo tres valores propios es muy regular. ^[5]

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 de distancia transitiva .
• El gráfico de la torre cuadrada n  ×  n , es decir, el gráfico lineal de un gráfico bipartito completo equilibrado K _{n, n} , es un 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 gráfico completo K _n es un srg ( ).${\displaystyle {\binom {n}{2}},2(n-2),n-2,4}$
• Los gráficos de Chang son srg (28, 12, 6, 4), lo mismo que el gráfico lineal de K ₈ , pero estos cuatro gráficos no son isomorfos.
• El gráfico lineal de un cuadrilátero generalizado GQ (2, 4) es un srg (27, 10, 1, 5). De hecho, cada cuadrilátero generalizado de orden (s, t) da un gráfico fuertemente regular de esta manera: a saber, un srg ((s + 1) (st + 1), s (t + 1), s-1, t +1).
• El gráfico de Schläfli es un srg (27, 16, 10, 8). ^[6]
• 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 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 de Local McLaughlin es un srg (162, 56, 10, 24).
• El gráfico de Cameron es un srg (231, 30, 9, 3).
• El gráfico Berlekamp – van Lint – Seidel es un srg (243, 22, 1, 2).
• El gráfico de McLaughlin es un srg (275, 112, 30, 56).
• La gráfica 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 de arco transitivo autocomplementarios son muy regulares.

Una gráfica fuertemente regular se llama primitiva si tanto la gráfica como su complemento están conectados. Todos los gráficos anteriores son primitivos, de lo contrario μ = 0 o λ = k.

El problema de 99 gráficas de Conway pide la construcción de un srg (99, 14, 1, 2). Se desconoce si existe un gráfico con estos parámetros y John Horton Conway ha ofrecido un premio de $ 1000 por la solución a este problema. ^[7]

Gráficos sin triángulos, gráficos de Moore y gráficos geodésicos

Las gráficas fuertemente regulares con λ = 0 no tienen triángulos . Aparte de los gráficos completos en menos de 3 vértices y todos los gráficos bipartitos completos, los siete enumerados anteriormente (pentágono, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22 y Higman-Sims) son los únicos conocidos. Las gráficas fuertemente regulares con λ = 0 y μ = 1 son gráficas de Moore con circunferencia 5. Nuevamente las tres gráficas dadas arriba (pentágono, Petersen y Hoffman-Singleton), con parámetros (5, 2, 0, 1), (10, 3, 0, 1) y (50, 7, 0, 1), son los únicos conocidos. El único otro conjunto posible de parámetros que produce un gráfico de Moore es (3250, 57, 0, 1); se desconoce si tal gráfico existe y, de ser así, si es único o no. ^[8]

De manera más general, todo gráfico fuertemente regular con es un gráfico geodésico , un gráfico en el que cada dos vértices tiene una ruta más corta no ponderada única . ^[9] Las únicas gráficas conocidas fuertemente regulares son las gráficas de Moore. No es posible que tenga un gráfico de este tipo , pero aún 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 gráfico fuertemente regular , ^{[10] [11]} no se sabe si existen más o incluso si su número es finito. ^[9]${\displaystyle \mu =1}$${\displaystyle \mu =1}$${\displaystyle \lambda =1}$${\displaystyle \mu =1}$

Ver también

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

Notas

1. https://projecteuclid.org/euclid.pjm/1103035734 , RC Bose, Gráficos fuertemente regulares, geometrías parciales y diseños parcialmente equilibrados, Pacific J. Math 13 (1963) 389–419. (pág.122)
2. Brouwer, Andries E; Haemers, Willem H. Spectra of Graphs . pag. 101 Archivado el 16 de marzo de 2012 en la Wayback Machine.
3. Godsil, Chris; Royle, Gordon. Teoría de grafos algebraicos . Springer-Verlag Nueva York, 2001, pág. 218.
4. Cameron, PJ; van Lint, JH (1991), Diseños, gráficos, códigos y sus vínculos , Textos estudiantiles 22 de la Sociedad Matemática de Londres, Cambridge University Press, pág. 37 , ISBN 978-0-521-42385-4
5. Godsil, Chris; Royle, Gordon. Teoría de grafos algebraicos . Springer-Verlag, Nueva York, 2001, Lema 10.2.1.
6. Weisstein, Eric W. , "Gráfico de Schläfli" , MathWorld
7. Conway, John H. , Five $ 1,000 Problems (Update 2017) (PDF) , Enciclopedia en línea de secuencias de enteros , consultado el 12 de febrero de 2019
8. Dalfó, C. (2019), "Una encuesta sobre el gráfico 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 
9. 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 
10. Deutsch, J .; Fisher, PH (2001), "En gráficos muy regulares con ", European Journal of Combinatorics , 22 (3): 303–306, doi : 10.1006 / eujc.2000.0472 , MR 1822718${\displaystyle \mu =1}$ 
11. Belousov, IN; Makhnev, AA (2006), "En gráficos fuertemente regulares con y sus automorfismos", Doklady Akademii Nauk , 410 (2): 151-155, MR 2455371${\displaystyle \mu =1}$ 

Referencias

• 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 , Gráficos muy regulares en un máximo de 64 vértices.