Kleinovy grafy - Klein graphs
V matematický pole teorie grafů, Kleinovy grafy jsou dva různé, ale příbuzné pravidelné grafy, každý s 84 okraji. Každý může být vložen do orientovatelného povrch z rod 3, ve kterém tvoří duální grafy.
Kubický Kleinův graf
| (Kubický) Kleinův graf | |
|---|---|
 56-Kleinův graf | |
| Pojmenoval podle | Felix Klein |
| Vrcholy | 56 |
| Hrany | 84 |
| Poloměr | 6 |
| Průměr | 6 |
| Obvod | 7 |
| Automorfismy | 336 |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Tloušťka knihy | 3 |
| Číslo fronty | 2 |
| Vlastnosti | Symetrický Krychlový Hamiltonian Cayleyův graf |
| Tabulka grafů a parametrů | |
Tento graf je 3-běžný graf s 56 vrcholy a 84 hranami, pojmenovanými podle Felix Klein.
Je to Hamiltonovský graf. Má to chromatické číslo 3, chromatický index 3, poloměr 6, průměr 6 a obvod 7. 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.[1]
Může být vložen do rod -3 orientovatelné povrch (který může být reprezentován jako Kleinova kvartika ), kde tvoří „Kleinovu mapu“ s 24 sedmiúhelníkovými plochami, Schläfliho symbol {7,3}8.
Podle Podporovat sčítání lidu, Kleinův graf, označovaný jako F056B, je jediný kubický symetrický graf na 56 vrcholech, který není bipartitní.[2]
To lze odvodit z 28-vrcholu Coxeterův graf.[3]
Algebraické vlastnosti
Skupina automorfismu Kleinova grafu je skupina PGL2(7) objednávky 336, která máPSL2(7) jako normální podskupina. Tato skupina působí přechodně na své poloviční okraje, takže Kleinův graf je a symetrický graf.
The charakteristický polynom tohoto 56-vrcholového Kleinova grafu se rovná
Galerie
Alternativní kresba kubického Kleinova grafu, ukazující, že jde o Hamiltonian, s chromatický index 3.
7valentní Kleinův graf
| (7valentní) Kleinův graf | |
|---|---|
 24-Kleinův graf | |
| Pojmenoval podle | Felix Klein |
| Vrcholy | 24 |
| Hrany | 84 |
| Poloměr | 3 |
| Průměr | 3 |
| Obvod | 3 |
| Automorfismy | 336 |
| Chromatické číslo | 4 |
| Chromatický index | 7 |
| Vlastnosti | Symetrický Hamiltonian |
| Tabulka grafů a parametrů | |
Tento graf je 7-běžný graf s 24 vrcholy a 84 hranami, pojmenovanými podle Felix Klein.
Je to Hamiltonovský graf. Má to chromatické číslo 4, chromatický index 7, poloměr 3, průměr 3 a obvod 3.
Může být vložen do orientovatelného povrchu rodu 3, kde tvoří duální „Kleinovu mapu“ s 56 trojúhelníkovými plochami, Schläfliho symbol {3,7}8.[4]
Je to jedinečný vzdálenost-pravidelný graf s průnikovým polem ; není to však vzdálenost-tranzitivní graf.[5]
Algebraické vlastnosti
Automorfická skupina 7valentního Kleinova grafu je stejná skupina řádu 336 jako pro kubickou Kleinovu mapu, která rovněž přechodně působí na své poloviční okraje.
The charakteristický polynom tohoto 24-vrcholového Kleinova grafu se rovná .[6]
Reference
- ^ Wolz, Jessica; Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Conder, M.; Dobcsányi, P. (2002), „Trojmocné symetrické grafy až do 768 vrcholů“, J. Combin. Matematika. Kombinovat. Comput., 40: 41–63.
- ^ Dejter, Italo. "Od Coxeterova grafu po Kleinův graf". CiteSeer. CiteSeerX 10.1.1.188.2580. Citovat deník vyžaduje
| deník =(Pomoc) - ^ Schulte, Egon; Wills, J. M. (1985). „Polyhedrální realizace mapy Felixe Kleina {3, 7}8 na Riemannově povrchu rodu 3 ". J. London Math. Soc. s2-32 (3): 539–547. doi:10.1112 / jlms / s2-32.3.539.
- ^ Brouwer, Andries; Cohen, Arjeh; Neumaier, Arnold (1989). Vzdálené pravidelné grafy. Springer-Verlag. p.386. ISBN 978-0-387-50619-7.
- ^ van Dam, E. R .; Haemers, W. H .; Koolen, J. H .; Spence, E. (2006). "Charakterizace pravidelnosti vzdálenosti grafů spektrem". J. Combin. Theory Ser. A. 113 (8): 1805–1820. doi:10.1016 / j.jcta.2006.03.008.