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
Klein graph.svg
56-Kleinův graf
Pojmenoval podleFelix Klein
Vrcholy56
Hrany84
Poloměr6
Průměr6
Obvod7
Automorfismy336
Chromatické číslo3
Chromatický index3
Tloušťka knihy3
Číslo fronty2
VlastnostiSymetrický
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

7valentní Kleinův graf

(7valentní) Kleinův graf
Klein-graf-7-valentní Hamiltonian.svg
24-Kleinův graf
Pojmenoval podleFelix Klein
Vrcholy24
Hrany84
Poloměr3
Průměr3
Obvod3
Automorfismy336
Chromatické číslo4
Chromatický index7
VlastnostiSymetrický
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

  1. ^ Wolz, Jessica; Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
  2. ^ Conder, M.; Dobcsányi, P. (2002), „Trojmocné symetrické grafy až do 768 vrcholů“, J. Combin. Matematika. Kombinovat. Comput., 40: 41–63.
  3. ^ Dejter, Italo. "Od Coxeterova grafu po Kleinův graf". CiteSeer. CiteSeerX  10.1.1.188.2580. Citovat deník vyžaduje | deník = (Pomoc)
  4. ^ 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.
  5. ^ Brouwer, Andries; Cohen, Arjeh; Neumaier, Arnold (1989). Vzdálené pravidelné grafy. Springer-Verlag. p.386. ISBN  978-0-387-50619-7.
  6. ^ 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.