Gráfico fuertemente regular

En la teoría de grafos, un gráfico fuertemente regular es un gráfico que tiene las siguientes propiedades:

Sea un grafo regular con vértices y grado . Se dice que es fuertemente regular si hay números enteros y tales que: $G=(V,E)$ $v$ $k$ $GRAMO$ $\lambda$ $\mu$

Dos vértices adyacentes cualesquiera tienen vecinos comunes. $\lambda$

Dos vértices cualesquiera no adyacentes tienen vecinos comunes. $\mu$

Los gráficos de este tipo a veces se denotan como . $srg(v,k,\lambda,\mu)$

Algunos autores excluyen grafos que satisfacen las condiciones trivialmente, a saber, grafos que son una unión disjunta de uno o más grafos completos del mismo tamaño [1] [2] , y sus complementos , grafos de Turan .

Un gráfico fuertemente regular es regular en distancia con diámetro , pero solo si es distinto de cero. $2$ $\mu$

Propiedades

Los cuatro parámetros en no son independientes y deben cumplir la siguiente condición: $srg(v,k,\lambda,\mu)$

{\ estilo de visualización (vk-1) \ mu = k (k- \ lambda -1)}

Esta condición se puede obtener de manera muy simple contando los argumentos de la siguiente manera:

Imagina los vértices del gráfico en tres niveles. Elijamos cualquier vértice como raíz, nivel . Entonces sus vértices vecinos se encuentran en el nivel , y todos los vértices restantes se encuentran en el nivel . ${\ estilo de visualización 0}$ $k$ $una$ $2$
Los vértices del nivel están conectados directamente a la raíz y, por lo tanto, deben tener otros vecinos que sean vecinos de la raíz, y estos vecinos también deben estar en el nivel . Dado que cada vértice tiene un grado , hay aristas que conectan cada vértice de nivel con el nivel . $una$ $\lambda$ $una$ $k$ $k-\lambda-1$ $una$ $2$
Los vértices del nivel no están conectados directamente a la raíz y, por lo tanto, deben tener vecinos comunes con la raíz, y todos estos vecinos deben estar en el nivel . Así, los vértices de nivel están conectados a cada vértice de nivel y cada uno de los vértices de nivel 1 está conectado a los vértices de nivel . Obtenemos que el número de vértices en el nivel es igual a . $2$ $\mu$ $una$ $\mu$ $una$ $2$ $k$ $k-\lambda-1$ $2$ $2$ $k(k-\lambda -1)/\mu$
El número total de vértices en los tres niveles, por lo tanto, es igual y después de la transformación, obtenemos . $v=1+k+k(k-\lambda -1)/\mu$ ${\ estilo de visualización (vk-1) \ mu = k (k- \ lambda -1)}$

Denotemos la matriz identidad (de orden ) y denotemos la matriz cuyos elementos son todos iguales a . La matriz de adyacencia de un gráfico fuertemente regular tiene las siguientes propiedades: ${\ estilo de visualización \ mathbf {yo}}$ $v$ ${\ estilo de visualización \ mathbf {J}}$ $una$ ${\matemáticas A}$
- $\mathbf {A} \mathbf {J} =k\mathbf {J}$
  (Esta es una paráfrasis trivial del requisito de que el grado de los vértices sea igual a ). $k$
- ${\mathbf {A} }^{2}+(\mu -\lambda ){\mathbf {A} }+(\mu -k){\mathbf {I} }=\mu {\mathbf { J} }$
  (El primer término, , da el número de caminos de dos saltos desde cualquier vértice a todos los vértices. El segundo término, , corresponde a aristas directamente conectadas. El tercer término, , corresponde a pares triviales cuando los vértices en el par son iguales ). ${\mathbf{A} }^{2}$ ${\ estilo de visualización (\ mu - \ lambda) {\ mathbf {A}))$ $(\mu-k){\mathbf{I} }$

El gráfico tiene exactamente tres valores propios :
- $k$ , cuya multiplicidad es igual a 1
- ${\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )))\ Correcto]$ , cuya multiplicidad es igual a ${\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
- ${\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )))\ Correcto]$ , cuya multiplicidad es igual a ${\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$

Grafos fuertemente regulares a los que se les llama grafos de conferencia debido a su conexión con matrices de conferencia simétricas . El número de parámetros independientes de estos gráficos se reduce a uno . $2k+(v-1)(\lambda -\mu )=0$ $srg\left(v,{\frac {v-1}{2)),{\frac {v-5}{4)),{\frac {v-1}{4))\right)$

Gráficas fuertemente regulares para las cuales , tienen valores propios enteros con multiplicidades desiguales. $2k+(v-1)(\lambda -\mu )\neq 0$

La adición también es fuertemente regular, lo es . $srg(v,k,\lambda,\mu)$ $srg(v,vk-1,v-2-2k+\mu,v-2k+\lambda)$

Ejemplos

$srg(5,2,0,1)$ — Ciclo de longitud 5;
$srg(10,3,0,1)$ - Conde Petersen ;
$srg(16,5,0,2)$ - Conde Clebsha ;
$srg(16,6,2,2)$ — Count Shrikhande , que no es transitivo a distancia ;
$srg(27,10,1,5)$ - Gráfico lineal de un cuadrilátero generalizado ; ${\ estilo de visualización GQ (2,4)}$
$srg(27,16,10,8)$ - Conde Schläfli [3] ;
$srg(28,12,6,4)$ — Condes de Chan ;
$srg(50,7,0,1)$ — El conde de Hoffman-Singleton ;
$srg(56,10,0,2)$ - Conde Gewirtz ;
$srg(77,16,0,4)$ - Cuenta M22 ;
$srg(81,20,1,6)$ - Conde Brouwer - Hemers ;
$srg(100,22,0,6)$ - Conde Higman - Sims ;
$srg(162,56,10,24)$ — Gráfico local de McLaughlin ;
$srg(q,{\frac {q-1}{2)),{\frac {q-5}{4)),{\frac {q-1}{4))))$ — La Orden del Conde de Paley ; $q$
$srg(n^{2},2n-2,n-2,2)$ es un gráfico de torre cuadrada . $n\veces n$

Se dice que un grafo fuertemente regular es simple si tanto el grafo como su complemento son conexos. Todos los gráficos anteriores son simples, ya que de lo contrario o . $\mu=0$ ${\ estilo de visualización \ mu = k}$

Condes de Moore

Gráficos fuertemente regulares que no contienen triángulos . Aparte de los gráficos completos con menos de 3 vértices y todos los gráficos bipartitos completos, los siete anteriores son gráficos conocidos de este tipo. Los gráficos fuertemente regulares con y son gráficos de Moore con circunferencia 5. Nuevamente, los tres gráficos anteriores, con parámetros , y , son los únicos gráficos conocidos de este tipo. El único otro conjunto de parámetros posible correspondiente a los gráficos de Moore es . No se sabe si tal gráfico existe y, de ser así, si es único. ${\ estilo de visualización \ lambda = 0}$ ${\ estilo de visualización \ lambda = 0}$ $\mu=1$ $srg(5,2,0,1)$ $srg(10,3,0,1)$ $srg(50,7,0,1)$ $srg(3250,57,0,1)$

Véase también

Matriz de adyacencia de Seidel

Notas

↑ Brouwer, 2012 , pág. 101.
↑ Godsil, 2001 , pág. 218.
↑ Weisstein, gráfico de Eric W. Schläfli (inglés) en el sitio web de Wolfram MathWorld .

Literatura

Brouwer AE, Cohen AM, Neumaier A. Gráficos regulares de distancia . - Berlín, Nueva York: Springer-Verlag, 1989. - ISBN 3-540-50619-5 .
Brouwer A.E., Haemers W.H. Spectra of Graphs (inglés) . - Nueva York: Springer-Verlag, 2012. - Vol. 418.- (Universitex). — ISBN 978-1-4614-1938-9 .
Godsil C., Royle G. Teoría de grafos algebraicos (inglés) . - Nueva York: Springer-Verlag, 2001. - ISBN 0-387-95241-1 .

Enlaces

Eric W. Weisstein , artículo de Mathworld con muchos ejemplos.
Gordon Royle , Lista de grandes gráficos y familias.
Andries E. Brouwer , Parámetros de grafos fuertemente regulares.
Brendan McKay , Colección de gráficos.
Ted Spence, Gráficos fuertemente regulares en un máximo de 64 vértices.