Gráfico de Dyck

En el campo matemático de la teoría de grafos , el grafo de Dyck es un grafo 3-regular con 32 vértices y 48 aristas, que recibe su nombre de Walther von Dyck . ^{[ 1 ] [ 2 ]}

Es hamiltoniano con 120 ciclos hamiltonianos distintos. Tiene número cromático 2, índice cromático 3, radio 5, diámetro 5 y circunferencia 6. También es un grafo 3 -conexo por vértices y 3 -conexo por aristas . Tiene grosor de libro 3 y número de cola 2. ^{[ 3 ]} El grafo es 1-planar . ^{[ 4 ]}

El grupo de automorfismos del grafo de Dyck es un grupo de orden 192. ^{[ 5 ]} Actúa transitivamente sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, el grafo de Dyck es un grafo simétrico . Posee automorfismos que transforman cualquier vértice en cualquier otro vértice y cualquier arista en cualquier otra arista. Según el censo de Foster , el grafo de Dyck, denominado F32A, es el único grafo cúbico simétrico de 32 vértices. ^{[ 6 ]}

El polinomio característico del gráfico de Dyck es igual a${\displaystyle (x-3)(x-1)^{9}(x+1)^{9}(x+3)(x^{2}-5)^{6}}$.

El grafo de Dyck es un grafo toroidal , contenido en el esqueleto de un mapa hexagonal regular , {6,3} _4,0 , con 32 vértices, 48 ​​aristas y 16 ciclos hexagonales. Es el dual de su incrustación toroidal simétrica, que es el grafo de Shrikhande .

Se puede visualizar como una red, una matriz de hexágonos de 4 por 4, donde los ejes izquierda-derecha y arriba-abajo se entrelazan formando un toroide plano.

El grafo de Dyck es el esqueleto de una teselación simétrica de una superficie de género tres por doce octágonos, conocida como mapa de Dyck o teselado de Dyck . El grafo dual para este teselado es el grafo tripartito completo K _4,4,4 . ^{[ 7 ] [ 8 ]}

• 
  Dibujo alternativo del gráfico de Dyck.
• 
  El número cromático del gráfico de Dyck es  2.
• 
  El índice cromático del gráfico de Dyck es  3.