Graf de Dyck

En matemàtiques, i més concretament en teoria de grafs, un graf de Dyck és un graf 3-regular no dirigit amb 32 vèrtexs i 48 arestes. Va ser definit pel matemàtic Walther von Dyck l'any 1881.^[1]^[2] Es tracta d'un graf hamiltonià amb 120 cicles diferents.

El graf de Dyck és toroidal, i el graf dual de la seva inserció toroidal simètrica és el graf de Shrikhande, un graf fortament regular tant simètric com hamiltonià.

Propietats algebraiques

El grup d'automorfisme del graf de Dyck és un grup d'ordre 192.^[3] Actua transitivament als vèrtexs, arestes i arcs del graf. Per tant, el graf de Dyck és simètric. Té automorfismes que poden passar qualsevol vèrtex a qualsevol altre, i qualsevol aresta a qualsevol altra. Segons el cens de Foster, el graf de Dyck (referenciat com F32A) és l'únic graf cúbic amb simetria en 32 vèrtexs.^[4]^[5]

El polinomi característic del graf de Dyck és $(x-3)(x-1)^{9}(x+1)^{9}(x+3)(x^{2}-5)^{6}$ .

Mapa de Dyck

El graf de Dyck és l'esquelet d'una tessel·lació simètrica, és a dir, del mapa regular d'una superfície tancada d'un genus de 3 x 12 octàgons, conegut com el mapa de Dyck o bé el tessel·lat de Dyck. El graf dual d'aquest mapa és el graf tripartit complet K_4,4,4.^[6]^[7]

Galeria

Representació alternativa del graf de Dyck.
El nombre cromàtic del graf de Dyck és 2.
L'índex cromàtic del graf de Dyck és 3.

Referències

↑ Dyck, W. «Über Aufstellung und Untersuchung von Gruppe und Irrationalität regulärer Riemann'scher Flächen». Math. Ann., 17, 1881, p. 473. DOI: 10.1007/bf01446929.
↑ Weisstein, Eric W., «Dyck Graph» a MathWorld (en anglès).
↑ Royle, G. F032A data^{[Enllaç no actiu]}
↑ Foster, Ronald M.; Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; Star, Z. The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs, 1988. ISBN 0-919611-19-2.
↑ Conder, M.; Dobcsányi, P. «Trivalent symmetric graphs up to 768 vertices». J. Combin. Math. Combin. Comput., 40, 2002, p. 41–63.
↑ Dyck, W. «Notiz über eine reguläre Riemannsche Fläche vom Geschlecht 3 und die zugehörige Normalkurve 4. Ordnung». Math. Ann., 17, 1880, p. 510–516. DOI: 10.1007/bf01446930.
↑ Ceulemans, A. «The tetrakisoctahedral group of the Dyck graph and its molecular realization.». Molecular Physics, 102, 11, 2004, p. 1149–1163. DOI: 10.1080/00268970410001728780.

[1] Dyck, W. «Über Aufstellung und Untersuchung von Gruppe und Irrationalität regulärer Riemann'scher Flächen». Math. Ann., 17, 1881, p. 473. DOI: 10.1007/bf01446929.

[2] Weisstein, Eric W., «Dyck Graph» a MathWorld (en anglès).

[3] Royle, G. F032A data^{[Enllaç no actiu]}

[4] Foster, Ronald M.; Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; Star, Z. The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs, 1988. ISBN 0-919611-19-2.

[5] Conder, M.; Dobcsányi, P. «Trivalent symmetric graphs up to 768 vertices». J. Combin. Math. Combin. Comput., 40, 2002, p. 41–63.

[6] Dyck, W. «Notiz über eine reguläre Riemannsche Fläche vom Geschlecht 3 und die zugehörige Normalkurve 4. Ordnung». Math. Ann., 17, 1880, p. 510–516. DOI: 10.1007/bf01446930.

[7] Ceulemans, A. «The tetrakisoctahedral group of the Dyck graph and its molecular realization.». Molecular Physics, 102, 11, 2004, p. 1149–1163. DOI: 10.1080/00268970410001728780.

[1]

[2]

[3]

[4]

[5]

[6]

[7]