Coxeterův graf - Coxeter graph
Coxeterův graf | |
---|---|
![]() Coxeterův graf | |
Pojmenoval podle | H. S. M. Coxeter |
Vrcholy | 28 |
Hrany | 42 |
Poloměr | 4 |
Průměr | 4 |
Obvod | 7 |
Automorfismy | 336 (PGL2(7)) |
Chromatické číslo | 3 |
Chromatický index | 3 |
Tloušťka knihy | 3 |
Číslo fronty | 2 |
Vlastnosti | Symetrický Vzdálenost-pravidelná Vzdálenost-tranzitivní Krychlový Hypohamiltonián |
Tabulka grafů a parametrů |
V matematický pole teorie grafů, Coxeterův graf je 3-běžný graf s 28 vrcholy a 42 hranami.[1] Je to jeden z 13 známých krychlový vzdálenost-pravidelné grafy.[2] Je pojmenován po Harold Scott MacDonald Coxeter.
Vlastnosti
Coxeterův graf má chromatické číslo 3, chromatický index 3, poloměr 4, průměr 4 a obvod 7. Je to také 3-graf spojený s vrcholem a 3-hranový graf. Má to tloušťka knihy 3 a číslo fronty 2.[3]
Coxeterův graf je hypohamiltonián: sám o sobě nemá Hamiltonovský cyklus, ale každý graf vytvořený odstraněním jediného vrcholu je Hamiltonian. Má to přímé číslo křížení 11 a je nejmenší kubický graf s tímto křížením[4] (sekvence A110507 v OEIS ).
Konstrukce
Nejjednodušší konstrukce Coxeterova grafu je z a Fano letadlo. Vezměte 7C3 = 35 možných 3 kombinací na 7 objektech. Zlikvidujte 7 tripletů, které odpovídají liniím Fano roviny, a ponechejte 28 tripletů. Propojte dvě trojice, pokud jsou disjunktní. Výsledkem je Coxeterův graf. Tato konstrukce vykazuje Coxeterův graf jako indukovaný podgraf z Kneserův graf KG7,3.
Coxeterův graf může být také sestaven z menší vzdálenosti - pravidelný Heawoodův graf konstrukcí vrcholu pro každý 6-cyklus v Heawoodově grafu a hranou pro každou disjunktní dvojici 6-cyklů.[5]
Coxeterův graf může být odvozen z Hoffman-Singletonův graf. Vezměte jakýkoli vrchol proti v grafu Hoffman-Singleton. Tady je nezávislá sada o velikosti 15, která zahrnuje proti. Smažte 7 sousedů z protia celá nezávislá sada včetně proti, zanechal Coxeterův graf.
Algebraické vlastnosti
Skupina automorfismu v Coxeterově grafu je skupina řádu 336.[6] Působí přechodně na vrcholy, na hrany a na oblouky grafu. Coxeterův graf je tedy 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, Coxeterův graf, označovaný jako F28A, je jediný kubický symetrický graf na 28 vrcholech.[7]
Coxeterův graf je také jednoznačně určen jeho grafové spektrum, množina vlastních čísel grafu matice sousedství.[8]
Jako konečný připojený vrchol-tranzitivní graf, který neobsahuje žádné Hamiltonovský cyklus, Coxeterův graf je protikladem k variantě Lovász dohad, ale kanonická formulace domněnky žádá o Hamiltonovu cestu a je ověřena Coxeterovým grafem.
Je známo pouze pět příkladů grafu tranzitivního po vrcholu bez hamiltonovských cyklů: kompletní graf K.2, Petersenův graf, Coxeterův graf a dva grafy odvozené z Petersenových a Coxeterových grafů nahrazením každého vrcholu trojúhelníkem.[9]
The charakteristický polynom Coxeterova grafu je . Je to jediný graf s tímto charakteristickým polynomem, což z něj dělá graf určený svým spektrem.
Galerie
Graf získaný jakoukoli excizí hrany z Coxeteru je spojen Hamiltonem.
The chromatické číslo Coxeterova grafu je 3.
The přímé číslo křížení Coxeterova grafu je 11.
Reference
- ^ Weisstein, Eric W. „Coxeter Graph“. MathWorld.
- ^ Brouwer, A.E .; Cohen, A. M .; a Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
- ^ Wolz, Jessica; Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Haythorpe, Michael; Newcombe, Alex (2018), Na 26 vrcholech s křížením číslo 11 nejsou žádné kubické grafy, arXiv:1804.10336
- ^ Dejter, Italo J. (2011), „From the Coxeter graph to the Klein graph“, Journal of Graph Theory, arXiv:1002.1960, doi:10,1002 / jgt.20597.
- ^ Royle, G. Data F028A[trvalý mrtvý odkaz ]
- ^ Conder, M. a Dobcsányi, P. „Trivalentní symetrické grafy až do 768 vrcholů.“ J. Combin. Matematika. Kombinovat. Comput. 40, 41-63, 2002.
- ^ E. R. van Dam a W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraická kombinace. 15, strany 189-202, 2003
- ^ Royle, G. „Krychlové symetrické grafy (pěstounské sčítání).“
- Coxeter, H. S. M. „Můj graf.“ Proc. London Math. Soc. 46, 117-136, 1983.