En el campo matemático de la teoría de grafos , el grafo de Dyck es un grafo regular de 32 vértices y 48 aristas, llamado así en honor a Walther von Dyck . [1] [2]
Es un 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 conexo por 3 vértices y conexo por 3 aristas . Tiene un grosor de libro de 3 y un número de cola de 2. [3]
El gráfico de Dyck es un gráfico toroidal ; el dual de su incrustación toroidal simétrica es el gráfico de Shrikhande .
El grupo de automorfismos del grafo de Dyck es un grupo de orden 192. [4] Actúa transitivamente sobre los vértices, sobre las aristas y sobre los arcos del grafo. Por tanto, el grafo de Dyck es un grafo simétrico . Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista. Según el censo de Foster , el grafo de Dyck, referenciado como F32A, es el único grafo cúbico simétrico sobre 32 vértices. [5]
El polinomio característico del gráfico de Dyck es igual a .
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 teselación de Dyck . El grafo dual para esta teselación es el grafo tripartito completo K 4,4,4 . [6] [7]
