Hispanopedia WikiEn 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 .
Propiedades algebraicas
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 .
Mapa de Dyck
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]
Galería
-
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.
Referencias
- ^ Dyck, W. (1881), "Über Aufstellung und Untersuchung von Gruppe und Irrationalität regulärer Riemann'scher Flächen", Math. Ana. , 17 (4): 473, doi :10.1007/bf01446929, S2CID 122956853.
- ^ Weisstein, Eric W. "Gráfico Dyck". MundoMatemático .
- ^ Wolz, Jessica; Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
- ^ "GG", Enciclopedia de gráficos , consultado el 26 de febrero de 2024
- ^ Conder, M. ; Dobcsányi, P. (2002), "Grafos simétricos trivalentes de hasta 768 vértices", J. Combin. Math. Combin. Comput. , 40 : 41–63.
- ^ Dyck, W. (1880), "Notiz über eine reguläre Riemannsche Fläche vom Geschlecht 3 und die zugehörige Normalkurve 4. Ordnung", Math. Ana. , 17 : 510–516, doi : 10.1007/bf01446930, S2CID 121904710.
- ^ Ceulemans, A. (2004), "El grupo tetrakisoctahedral del grafo de Dyck y su realización molecular.", Molecular Physics , 102 (11): 1149–1163, doi :10.1080/00268970410001728780, S2CID 97973403.