Grafo de Shrikhande

No grafo de Shrikhande, quaisquer dois vértices I e J têm dois vizinhos distintos em comum (excluindo os próprios dois vértices I e J), o que é verdade independentemente de I ser adjacente a J. Em outras palavras, seus parâmetros para ser fortemente regulares são: {16,6,2,2}, com ${\displaystyle \lambda =\mu =2}$, esta igualdade implicando que o grafo é associado a um BIBD simétrico. Ele compartilha esses parâmetros com um grafo diferente, o 4×4 grafo torre (rook's graph).

O grafo de Shrikhande é localmente hexagonal; isto é, os vizinhos de cada vértice formam um grafo ciclo de seis vértices. Como em qualquer grafo localmente cíclico, o grafo de Shrikhande é o 1-esqueleto de uma triangulação de Whitney de alguma superfície; no caso do grafo de Shrikhande, esta superfície é um toro em que cada vértice é cercado por seis triângulos.[2] Assim, o grafo de Shrikhande é um grafo toroidal. O dual desta incorporação é o grafo de Dick, um grafo cúbico simétrico.

O grafo de Shrikhande não é um grafo distância-transitivo. É o menor grafo distância-regular que não é a distância-transitivo.[3]

O grupo de automorfismo do grafo de Shrikhande é da ordem de 192. Ele age transitivamente sobre os vértices, nas arestas e nos arcos do grafo.

O polinômio característico do grafo de Shrikhande é: ${\displaystyle (x-6)(x-2)^{6}(x+2)^{9}}$. Portanto o grafo de Shrikhande é um grafo integral: seu espectro consiste inteiramente de inteiros.

• «O grafo de Shrikhande». , Peter Cameron, Agosto de 2010.

• 
  O grafo de Shrikhande é um grafo toroidal.
• 
  O número cromático do grafo de Shrikhande é 4.
• 
  O índice cromático do grafo de Shrikhande é 6.
• 
  O grafo de Shrikhande desenhado simetricamente.
• 
  O grafo de Shrikhande é Hamiltoniano.