Gráfico de Shrikhande

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 , con cada vértice teniendo grado  6. Cada par de nodos tiene exactamente otros dos vecinos en común, independientemente de si el par de nodos está conectado o no.

El grafo de Shrikhande se puede construir como un grafo de Cayley . El conjunto de vértices es${\displaystyle \mathbb {Z} _{4}\times \mathbb {Z} _{4}}$Dos vértices son adyacentes si y solo si la diferencia es${\displaystyle \{\pm (1,0),\pm (0,1),\pm (1,1)\}}$.

En el grafo de Shrikhande, cualesquiera dos vértices distintos I y J tienen dos vecinos en común, lo cual se cumple 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}, con${\displaystyle \lambda =\mu =2}$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 torres de 4 × 4 , es decir, el grafo de líneas L ( K _4,4 ) del grafo bipartito completo K _4,4 . Este último grafo es el único grafo de líneas L ( K _n,n ) para el cual los parámetros de regularidad fuerte no determinan ese grafo de forma única, sino que se comparten con un grafo diferente. ^{[ 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 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 incrustado en el toro) es el grafo de Dyck , un grafo cúbico simétrico.

El grafo de Shrikhande no es un grafo transitivo en distancia . Es el grafo regular en distancia más pequeño que no es transitivo en distancia. ^{[ 5 ]}

El grupo de automorfismos del grafo de Shrikhande es de orden 192. Actúa transitivamente sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, el grafo de Shrikhande es un grafo simétrico .

El polinomio característico del gráfico de Shrikhande es${\displaystyle (x-6)(x-2)^{6}(x+2)^{9}}$Por lo tanto, el grafo de Shrikhande es un grafo integral : su espectro consta enteramente de números enteros.

Tiene un grosor de libro de 4 y un número de cola de 3. ^{[ 6 ]}

El gráfico no es 1-planar . ^{[ 7 ]}

• 
  El gráfico de Shrikhande es un gráfico toroidal .
• 
  El número cromático del gráfico de Shrikhande es  4.
• 
  El índice cromático del gráfico de Shrikhande es  6.
• 
  El gráfico de Shrikhande dibujado simétricamente.
• 
  El grafo de Shrikhande es hamiltoniano .

• Holton, DA; Sheehan, J. (1993), The Petersen Graph , Cambridge University Press , pág.  270, ISBN 0-521-43594-3.

• El gráfico de Shrikhande , Peter Cameron , agosto de 2010.