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[modifica]
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 .
Mapa de Dyck[modifica]
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 K4,4,4.[6][7]
Galeria[modifica]
-
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[modifica]
- ↑ 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.