Conde de Srikhande

El conde de Shrikhande  es un recuento encontrado por SS Shrikhande ( inglés ) en 1959 [1] [2] . El gráfico es fuertemente regular , tiene 16 vértices y 48 aristas , y cada vértice tiene grado 6. Cada par de nodos tiene exactamente dos vecinos comunes, ya sea que el par esté o no conectado por una arista.

Edificio

El gráfico de Shrikhande se puede construir como un gráfico de Cayley en el que el conjunto de vértices es , y dos vértices están conectados si y solo si la diferencia está en .

Propiedades

En el gráfico de Shrikhand, dos vértices I y J tienen dos vecinos comunes diferentes (excluyendo los vértices I y J ), lo cual es cierto ya sea que I y J sean adyacentes o no. En otras palabras, el gráfico es fuertemente regular y sus parámetros son: {16,6,2,2}, es decir, . De esta igualdad se deduce que el gráfico está asociado con diseños de bloques incompletos equilibrados simétricos ( ing. Diseños de bloques incompletos equilibrados , BIBD). El gráfico de Shrikhande comparte estos parámetros exactamente con otro gráfico, el gráfico de torre de 4×4 , es decir, el gráfico lineal L ( K 4,4 ) del gráfico bipartito completo K 4,4 . El último gráfico es el único gráfico de líneas L ( K n, n ) para el cual los parámetros de regularidad fuertes no definen de manera única este gráfico, y el gráfico los comparte con otro gráfico, a saber, el gráfico de Shrikhande (que no es un gráfico de torre) [ 2] [3 ] .  

El gráfico de Srikhande es localmente hexagonal . Es decir, los vecinos de cada vértice forman un ciclo de seis vértices. Como cualquier gráfico localmente cíclico, el gráfico de Shrikhande es el esqueleto de 1 la 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] Así, el grafo de Shrikhande es un grafo toroidal . La incrustación forma un mapeo regular en un toro con 32 caras triangulares. El esqueleto del gráfico dual de este mapeo (incrustado en un toro) es el gráfico de Dyck , un gráfico simétrico cúbico.

El gráfico de Shrikhande no es transitivo en distancia . Este es el gráfico regular de distancia más pequeño que no es transitivo de distancia [5] .

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

El polinomio característico del gráfico de Shrikhande es . Por lo tanto, el gráfico de Shrikhande es un gráfico completo  : su espectro consiste completamente en números enteros.

El gráfico tiene grosor de libro 4 y número de colas 3 [6] .

Galería

• El gráfico de Srikhande es toroidal .

• El número cromático del Conde Srikhande es 4.

• El índice cromático del Conde Shrikhande es 6.

• El Conde de Srikhande, dibujado simétricamente.

• Conde Srikhande de los Hamilton .

Notas

1. ↑ Weisstein, Eric W. Shrikhande Gráfico  en el sitio web Wolfram MathWorld .
2. ↑ 1 2 Shrikhande, 1959 , pág. 781–798.
3. ↑ Harary, 1972 , pág. 79.
4. ↑ Gráfico de Brouwer AE Shrikhande Archivado el 9 de marzo de 2014 en Wayback Machine .
5. ↑ Brouwer, Cohen, Neumaier 1989 , pág. 104–105, 136.
6. ↑ Volz, 2018 .

Literatura

• Shrikhande SS La singularidad del esquema de asociación L 2  // Annals of Mathematical Statistics. - 1959. - T. 30 . — S. 781–798 . -doi : 10.1214 / aoms/1177706207 . — .
• Frank Harary. teoría de grafos . —Massachusetts: Addison-Wesley, 1972.
  • Harari F. Teoría de grafos. - M. : "Mir", 1973.
• , ISBN 0-521-43594-3 
• Brouwer AE, Cohen AM, Neumaier A. Gráficos de distancia regular. - Nueva York: Springer-Verlag, 1989. - S. 104-105, 136.
• Jessica Walz. Ingeniería de Trazados Lineales con SAT. - Universidad de Tübingen, 2018. - (Tesis de Maestría).

Enlaces

• The Shrikhande Graph Archivado el 24 de noviembre de 2010 en Wayback Machine , Peter Cameron, agosto de 2010.