Gráfico de Shrikhande

Gráfico de Shrikhande
El gráfico de Shrikhande
Lleva el nombre de	SS Shrikhande
Vértices	dieciséis
Bordes	48
Radio	2
Diámetro	2
Circunferencia	3
Automorfismos	192
Número cromático	4
Índice cromático	6
Espesor del libro	4
Número de cola	3
Propiedades	Integral euleriana simétrica hamiltoniana muy regular
Tabla de gráficos y parámetros

En el campo matemático de la teoría de grafos , el grafo de Shrikhande es un grafo con nombre descubierto por SS Shrikhande en 1959. ^{[1] [2]} Es un grafo fuertemente regular con 16 vértices y 48 aristas , con cada vértice de grado  6. Cada par of nodos tiene exactamente otros dos vecinos en común, tanto si el par de nodos está conectado como si no.

Construcción

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 .${\displaystyle \mathbb {Z} _{4}\times \mathbb {Z} _{4}}$${\displaystyle \{\pm (1,0),\pm (0,1),\pm (1,1)\}}$

Propiedades

En el gráfico de Shrikhande, cualesquiera dos vértices I y J tienen dos vecinos distintos en común (excluyendo los dos vértices I y J en sí mismos), lo que es válido tanto si I es adyacente a J como si no . En otras palabras, es muy normal y sus parámetros son: {} 16,6,2,2, es decir, . Esta igualdad implica que el gráfico está asociado con un BIBD simétrico . El gráfico de Shrikhande comparte estos parámetros con exactamente otro gráfico, el gráfico de torre de 4 × 4 , es decir, el gráfico lineal L ( K _4,4 ) del${\displaystyle \lambda =\mu =2}$ gráfico bipartito completo K _4,4 . El último gráfico es el único gráfico lineal L ( K _{n, n} ) para el cual los parámetros de regularidad fuerte no determinan ese gráfico de forma única, sino que se comparten con un gráfico diferente, a saber, el gráfico de Shrikhande (que no es un gráfico de torre). ^{[2] [3]}

El gráfico de Shrikhande es localmente hexagonal ; es decir, los vecinos de cada vértice forman un ciclo de seis vértices. Como ocurre con cualquier gráfico localmente cíclico, el gráfico de Shrikhande es el esqueleto 1 de una triangulación de Whitney de alguna superficie; en el caso del gráfico de Shrikhande, esta superficie es un toro en el que cada vértice está rodeado por seis triángulos. ^[4] Por lo tanto, el gráfico de Shrikhande es un gráfico toroidal . La incrustación forma un mapa regular en el toro, con 32 caras triangulares. El esqueleto del dual de este mapa (incrustado en el toro) es el gráfico de Dyck , un gráfico simétrico cúbico.

El gráfico de Shrikhande no es un gráfico transitivo a la distancia . Es el gráfico de distancia regular más pequeño que no es transitivo a la distancia. ^[5]

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

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

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

Galería

• 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 gráfico de Shrikhande es hamiltoniano .

Notas

1. Weisstein, Eric W. "Gráfico de Shrikhande" . MathWorld .
2. Shrikhande, SS (1959), "La singularidad del esquema de asociación L ₂ ", Annals of Mathematical Statistics , 30 : 781–798, doi : 10.1214 / aoms / 1177706207 , JSTOR 2237417 .
3. Harary, F. (1972), "Teorema 8.7", Teoría de grafos (PDF) , Massachusetts: Addison-Wesley, p. 79 .
4. Brouwer, gráfico de AE Shrikhande .
5. Brouwer, AE; Cohen, AM; Neumaier, A. (1989), Distance-Regular Graphs , Nueva York: Springer-Verlag, págs. 104-105 y 136.
6. Jessica Wolz, Diseños lineales de ingeniería con SAT . Tesis de maestría, Universidad de Tübingen, 2018

Referencias

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

enlaces externos

• The Shrikhande Graph , Peter Cameron , agosto de 2010.