Contele Wagner

Graficul Wagner  este un graf regulat de 3 cu 8 vârfuri și 12 muchii [1] și este o scară Möbius cu 8 vârfuri .

Proprietăți

Ca toate scările Möbius, graficul Wagner nu este plan , dar numărul său de trecere este unul, făcându-l apical . Un grafic poate fi încorporat fără auto-intersecții pe un torus sau un plan proiectiv , astfel încât să fie toroidal . Circumscripția sa este 4, diametrul este 2, raza este 2, numărul cromatic  este 3, indicele cromatic  este 3. Graficul este atât vârf-3-conectat , cât și margine-3-conectat .

Graficul Wagner are 392 de arbori spanning . Acest grafic și graficul complet K 3,3 au cel mai mare număr de arbori spanning dintre toate graficele cubice cu același număr de vârfuri [2] .

Graficul Wagner este tranzitiv la vârf , dar nu tranzitiv la muchie . Grupul său de automorfism complet este izomorf cu grupul diedric de ordinul al 16-lea D8 , grupul de simetrie octogon , incluzând atât rotațiile, cât și reflexiile.

Polinomul caracteristic al graficului Wagner este . Acesta este singurul grafic care are un astfel de polinom, în urma căruia graficul este determinat în mod unic de spectru.

Graficul Wagner nu conține triunghiuri și mulțimea sa independentă de vârfuri este trei, ceea ce reprezintă jumătate din dovada că numărul Ramsey este R (3,4) (cel mai mic număr n astfel încât orice grafic cu n vârfuri conține fie un triunghi, fie un independent mulţime de patru vârfuri) este 9 [3] .

Numărați minorii

Scările Möbius joacă un rol important în teoria grafurilor minore . Cel mai vechi rezultat de acest tip este teorema din 1937 a lui Klaus Wagner (parte a unui grup de rezultate cunoscut sub numele de teorema lui Wagner ) conform căreia grafice care nu conțin K 5 minori pot fi formate folosind sume de clicuri ale grafurilor plane și scara M 8 Möbius [4 ] . Din acest motiv, M 8 este numit graficul Wagner.

Graficul Wagner este unul dintre cele patru minore minime interzise pentru graficele cu lățimea arborelui de cel mult trei (celelalte trei sunt graficul K 5 complet , graficul octaedrului obișnuit și graficul cu prismă pentagonală ) și unul dintre cele patru minore minime interzise pentru grafice. cu lățimi ale ramurilor de cel mult trei (celelalte trei sunt K 5 , graficul octaedric și graficul cub [5] [6] .

Clădire

Graficul Wagner este cubic și hamiltonian și are notația LCF [4] 8 .

Graficul poate fi construit ca o scară cu patru trepte pe un ciclu al unei benzi topologice Möbius .

Galerie

• Numărul cromatic al contelui Wagner este 3.

• Indicele cromatic al graficului Wagner este 3.

• Graficul Wagner sub forma unei benzi Möbius.

Note

1. ↑ JA Bondy, USR Murty. teoria grafurilor. - Springer, 2007. - S. 275-276. - ISBN 978-1-84628-969-9 .
2. ↑ Dmitry Jakobson, Igor Rivin. Despre unele probleme extreme din teoria grafurilor. — 1999.
3. ↑ Soif Alexandru. Cartea de colorat matematic. - 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 , nr. 1 . — S. 570–590 . - doi : 10.1007/BF01594196 .
5. ↑ Hans L. Bodlaender. Un k -arboretum parțial de grafice cu lățime de arbore mărginită // Informatică teoretică. - 1998. - T. 209 , nr. 1–2 . — S. 1–45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
6. ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Grafice cu lățimea ramurilor de cel mult trei // Journal of Algorithms. - 1999. - T. 32 , nr. 2 . — S. 167–194 . - doi : 10.1006/jagm.1999.1011 . .