En el campo matemático de la teoría de grafos , el grafo de Shrikhande es un grafo descubierto por SS Shrikhande en 1959. [1] [2] Es un grafo fuertemente regular con 16 vértices y 48 aristas , y cada vértice tiene grado 6. Cada par de nodos tiene exactamente otros dos vecinos en común, independientemente de que el par de nodos esté conectado o no.
El gráfico de Shrikhande se puede construir como un gráfico de Cayley . El conjunto de vértices es . Dos vértices son adyacentes si y solo si la diferencia está en .
En el grafo de Shrikhande, dos vértices cualesquiera I y J tienen dos vecinos distintos en común (excluyendo los dos vértices I y J mismos), lo cual es cierto independientemente de si I es adyacente a J o no . En otras palabras, es fuertemente regular y sus parámetros son: {16,6,2,2}, es decir, . Esta igualdad implica que el grafo está asociado con un BIBD simétrico . El grafo de Shrikhande comparte estos parámetros con exactamente otro grafo, el grafo de torre 4×4 , es decir, el grafo lineal L ( K 4,4 ) del grafo bipartito completo K 4,4 . Este último grafo es el único grafo lineal L ( K n,n ) para el cual los parámetros de regularidad fuerte no determinan ese grafo de manera única, sino que se comparten con un grafo diferente, a saber, el grafo de Shrikhande (que no es un grafo de torre). [2] [3]
El grafo de Shrikhande es localmente hexagonal ; es decir, los vecinos de cada vértice forman un ciclo de seis vértices. Como con cualquier grafo localmente cíclico, el grafo de Shrikhande es el 1-esqueleto de una triangulación de Whitney de alguna superficie; en el caso del grafo de Shrikhande, esta superficie es un toro en el que cada vértice está rodeado por seis triángulos. [4] Por lo tanto, el grafo de Shrikhande es un grafo toroidal . La incrustación forma un mapa regular en el toro, con 32 caras triangulares. El esqueleto del dual de este mapa (como está incrustado en el toro) es el grafo de Dyck , un grafo cúbico simétrico.
El gráfico de Shrikhande no es un gráfico transitivo en función de la distancia . Es el gráfico regular en función de la distancia más pequeño que no es transitivo en función de la distancia. [5]
El grupo de automorfismos del grafo de Shrikhande es de orden 192. Actúa transitivamente sobre los vértices, sobre las aristas y sobre los arcos del grafo. Por lo tanto, el grafo de Shrikhande es un grafo simétrico .
El polinomio característico del grafo de Shrikhande es: . Por lo tanto, el grafo de Shrikhande es un grafo integral : su espectro está formado enteramente por números enteros.
Tiene un grosor de libro de 4 y un número de cola de 3. [6]
