Wagner gróf

A Wagner-gráf  egy 3 reguláris gráf, 8 csúcsával és 12 élével [1] , és egy 8 csúcsú Möbius-létra .

Tulajdonságok

Mint minden Möbius-lépcső, a Wagner-gráf sem sík , hanem a keresztezési száma egy, ami apikálissá teszi . Egy gráf önmetszéspontok nélkül ágyazható be tóruszba vagy projektív síkra , így toroid alakú . kerülete 4, átmérője 2, sugara 2, kromatikus száma  3, kromatikus indexe  3. A gráf 3-as csúcshoz és él-3-hoz kapcsolódik .

A Wagner-gráf 392 feszítőfát tartalmaz . Ennek a gráfnak és a K 3,3 teljes gráfnak van a legtöbb feszítőfája az azonos számú csúcsú köbös gráfok közül [2] .

A Wagner-gráf csúcstranzitív , de nem éltranzitív . Teljes automorfizmuscsoportja izomorf a 16. rendű D8 diédercsoporttal , a nyolcszög szimmetriacsoporttal , beleértve a forgásokat és a tükröződéseket is.

A Wagner-gráf karakterisztikus polinomja : . Ez az egyetlen gráf, amely ilyen polinomot tartalmaz, aminek eredményeként a gráfot a spektrum egyedileg határozza meg.

A Wagner-gráf nem tartalmaz háromszögeket , és a független csúcskészlete három, ami fele annak a bizonyítéka, hogy a Ramsey-szám R (3,4) (a legkisebb n szám , amelyben minden n csúcsú gráf háromszöget vagy függetlenet tartalmaz négy csúcsból álló halmaz) 9 [3] .

Kiskorúak száma

A Möbius lépcsők fontos szerepet játszanak a gráfmollok elméletében . Ennek a típusnak a legkorábbi eredménye Klaus Wagner 1937-es tétele (a Wagner-tételként ismert eredménycsoport része ), amely szerint K 5 mollokat nem tartalmazó gráfok képezhetők síkgráfok klikkösszegei és az M 8 Möbius létra segítségével [4 ] . Emiatt M 8 - at Wagner-gráfnak nevezik.

A Wagner-gráf a legfeljebb három faszélességű gráfok négy minimálisan tiltott molljának egyike (a másik három a teljes K 5 gráf, a szabályos oktaéder gráf és az ötszögű prizmagráf ), valamint a gráfok négy minimálisan tiltott molljának egyike. legfeljebb három ágszélességgel (a másik három a K 5 , az oktaéder gráf és a kockagráf [5] [6] ) .

Épület

A Wagner-gráf köbös és Hamilton -féle , és LCF jelöléssel rendelkezik [4] 8 .

A gráf egy topologikus Möbius szalag ciklusán négy lépcsős létraként szerkeszthető .

Galéria

• Wagner gróf kromatikus száma 3.

• A Wagner-gráf kromatikus indexe 3.

• Wagner-gráf Möbius-szalag formájában.

Jegyzetek

1. ↑ JA Bondy, USR Murty. gráfelmélet. - Springer, 2007. - S. 275-276. - ISBN 978-1-84628-969-9 .
2. ↑ Dmitrij Jakobson, Igor Rivin. A gráfelmélet néhány extrém problémájáról. – 1999.
3. ↑ Szoif Sándor. A matematikai kifestőkönyv. - Springer-Verlag, 2008. - P. 245. - ISBN 978-0-387-74640-1 .
4. ↑ K. Wagner. Über eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. - 1937. - T. 114 , sz. 1 . — S. 570–590 . - doi : 10.1007/BF01594196 .
5. ↑ Hans L. Bodlaender. Korlátozott faszélességű gráfok részleges k -arborétuma // Elméleti számítástechnika. - 1998. - T. 209 , szám. 1–2 . – S. 1–45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
6. ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Legfeljebb három ágszélességű grafikonok // Journal of Algorithms. - 1999. - T. 32 , sz. 2 . – S. 167–194 . - doi : 10.1006/jagm.1999.1011 . .