Wagnerův graf - Wagner graph
| Wagnerův graf | |
|---|---|
 Wagnerův graf | |
| Pojmenoval podle | Klaus Wagner |
| Vrcholy | 8 |
| Hrany | 12 |
| Poloměr | 2 |
| Průměr | 2 |
| Obvod | 4 |
| Automorfismy | 16 (D8) |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Rod | 1 |
| Vlastnosti | Krychlový Hamiltonian Bez trojúhelníků Vrchol-tranzitivní Toroidní Vrchol |
| Zápis | M8 |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Wagnerův graf je 3-běžný graf s 8 vrcholy a 12 hranami.[1] Je to 8-vrchol Möbiový žebřík graf.
Vlastnosti
Jako Möbiový žebřík je Wagnerův graf neplanární ale má číslo křížení jeden, takže je vrcholový graf. Může být vložen bez křížení na a torus nebo projektivní rovina, takže je to také toroidní graf. Má obvod 4, průměr 2, poloměr 2, chromatické číslo 3, chromatický index 3 a oba jsou 3připojen k vrcholu a 3-připojeno k okraji.
Wagnerův graf má 392 klenout se nad stromy; to a kompletní graf K.3,3 mít nejvíce kostry mezi všemi kubickými grafy se stejným počtem vrcholů.[2]
Wagnerův graf je a vrchol-tranzitivní graf ale není hrana tranzitivní. Jeho úplná skupina automorfismu je isomorfní s dihedrální skupina D8 řádu 16, skupina symetrií an osmiúhelník, včetně rotací i odrazů.
The charakteristický polynom Wagnerova grafu je . Je to jediný graf s tímto charakteristickým polynomem, což z něj dělá graf určený svým spektrem.
Wagnerův graf je bez trojúhelníků a má číslo nezávislosti tři, poskytující polovinu důkazu, že Ramseyovo číslo R(3,4) (nejmenší počet n takový, že jakýkoli n-vertexový graf obsahuje buď trojúhelník, nebo čtyřvertex nezávislou množinu) je 9.[3]
Graf nezletilí
Möbiovy žebříky hrají důležitou roli v teorii nezletilí v grafu. Nejčasnějším výsledkem tohoto typu je věta z roku 1937 Klaus Wagner (část shluku výsledků známých jako Wagnerova věta ), že grafy s č K.5 menší lze vytvořit pomocí klika-součet operace kombinující rovinné grafy a Möbiový žebřík M8.[4] Z tohoto důvodu M8 se nazývá Wagnerův graf.
Wagnerův graf je také jedním ze čtyř minimálních zakázané nezletilé pro grafy šířka stromu maximálně tři (další tři jsou kompletní graf K.5, graf pravidelný osmistěn a graf pětiúhelníkový hranol ) a jeden ze čtyř minimálně zakázaných nezletilých pro grafy šířka větve maximálně tři (další tři jsou K.5, graf oktaedru a krychlový graf ).[5][6]
Konstrukce
Wagnerův graf je a krychlový Hamiltonovský graf a lze je definovat pomocí LCF notace [4]8. Jedná se o instanci Andrásfai graf, typ oběhový graf ve kterém mohou být vrcholy uspořádány v cyklu a každý vrchol je spojen s ostatními vrcholy, jejichž polohy se liší o číslo, které je 1 (mod 3). Je také izomorfní s kruhová klika K.8/3.
Může být nakreslen jako žebříkový graf se 4 příčkami cyklickými na topologii Möbiusův proužek.
Galerie
The chromatické číslo Wagnerova grafu je 3.
The chromatický index Wagnerova grafu je 3.
Wagnerův graf nakreslený na Möbiově pásu.
Reference
- ^ Bondy, J. A.; Murty, USA (2007). Teorie grafů. Springer. str. 275–276. ISBN 978-1-84628-969-9.CS1 maint: více jmen: seznam autorů (odkaz)
- ^ Jakobson, Dmitry; Rivin, Igor (1999). "O některých extrémních problémech v teorii grafů". arXiv:math.CO/9907050.
- ^ Soifer, Alexander (2008). Matematická omalovánka. Springer-Verlag. p. 245. ISBN 978-0-387-74640-1..
- ^ Wagner, K. (1937). „Über eine Eigenschaft der ebenen Komplexe“. Mathematische Annalen. 114 (1): 570–590. doi:10.1007 / BF01594196. S2CID 123534907.
- ^ Bodlaender, Hans L. (1998). „Částečné k-arboretum grafů s omezenou šířkou stromu ". Teoretická informatika. 209 (1–2): 1–45. doi:10.1016 / S0304-3975 (97) 00228-4. hdl:1874/18312..
- ^ Bodlaender, Hans L.; Thilikos, Dimitrios M. (1999). Msgstr "Grafy s maximální šířkou větve". Journal of Algorithms. 32 (2): 167–194. doi:10.1006 / jagm.1999.1011. hdl:1874/2734..