Dyckův graf - Dyck graph
| Dyckův graf | |
|---|---|
 Dyckův graf | |
| Pojmenoval podle | W. Dyck |
| Vrcholy | 32 |
| Hrany | 48 |
| Poloměr | 5 |
| Průměr | 5 |
| Obvod | 6 |
| Automorfismy | 192 |
| Chromatické číslo | 2 |
| Chromatický index | 3 |
| Tloušťka knihy | 3 |
| Číslo fronty | 2 |
| Vlastnosti | Symetrický Krychlový Hamiltonian Bipartitní Cayleyův graf |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Dyckův graf je 3-běžný graf s 32 vrcholy a 48 hranami, pojmenovanými podle Walther von Dyck.[1][2]
to je Hamiltonian se 120 odlišnými hamiltonovskými cykly. Má to chromatické číslo 2, chromatický index 3, poloměr 5, průměr 5 a obvod 6. Je to také 3-připojen k vrcholu a 3-připojeno k okraji graf. Má to tloušťka knihy 3 a číslo fronty 2.[3]
Dyckův graf je a toroidní graf a duál jeho symetrického toroidního vložení je Shrikhandův graf, silně pravidelný graf symetrický i hamiltonovský.
Algebraické vlastnosti
Skupina automorfismu v Dyckově grafu je skupina řádu 192.[4] Působí přechodně na vrcholy, na hrany a na oblouky grafu. Proto je Dyckův graf a symetrický graf. Má automatorfismy, které berou jakýkoli vrchol na jakýkoli jiný vrchol a jakoukoli hranu na jakoukoli jinou hranu. Podle Podporovat sčítání lidu, Dyckův graf, označovaný jako F32A, je jediný kubický symetrický graf na 32 vrcholech.[5]
The charakteristický polynom Dyckova grafu se rovná .
Dyck mapa
Dyckův graf je kostra a symetrická mozaikování povrchu rod tři o dvanáct osmiúhelníků, známé jako Dyck mapa nebo Dyck obklady. The duální graf pro tento obklad je kompletní trojstranný graf K.4,4,4.[6][7]
Galerie
Alternativní kresba Dyckova grafu.
The chromatické číslo Dyckova grafu je 2.
The chromatický index Dyckova grafu je 3.
Reference
- ^ Dyck, W. (1881), „Über Aufstellung und Untersuchung von Gruppe und Irrationalität regulärer Riemann'scher Flächen“, Matematika. Ann., 17: 473, doi:10.1007 / bf01446929.
- ^ Weisstein, Eric W. „Dyck Graph“. MathWorld.
- ^ Wolz, Jessica; Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Royle, G. Data F032A[trvalý mrtvý odkaz ]
- ^ Conder, M.; Dobcsányi, P. (2002), „Trojmocné symetrické grafy až do 768 vrcholů“, J. Combin. Matematika. Kombinovat. 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“, Matematika. Ann., 17: 510–516, doi:10.1007 / bf01446930.
- ^ Ceulemans, A. (2004), „Tetrakisoctahedral skupina Dyckova grafu a její molekulární realizace.“, Molekulární fyzika, 102 (11): 1149–1163, doi:10.1080/00268970410001728780.