Grev Wagner

grev Wagner
Opkaldt efter Klaus Wagner
Toppe otte
ribben 12
Radius 2
Diameter 2
Omkreds fire
Automorfismer 16 ( D8 )
Kromatisk tal 3
Kromatisk indeks 3
Ejendomme

kubisk uden Hamiltonske
trekanter vertex-transitive toroidale



topmøde
 Mediefiler på Wikimedia Commons

Wagner-grafen  er en 3 -regulær graf med 8 hjørner og 12 kanter [1] og er en Möbius-stige med 8 hjørner .

Egenskaber

Som alle Möbius-trapper er Wagner-grafen ikke plan , men dens krydsningsnummer er ét, hvilket gør den apikal . En graf kan indlejres uden selvskæringer på et torus eller projektivt plan , så den er toroidformet . Dens omkreds er 4, diameter er 2, radius er 2, kromatisk tal  er 3, kromatisk indeks  er 3. Grafen er både toppunkt-3-forbundet og kant-3-forbundet .

Wagner-grafen har 392 spændende træer . Denne graf og den komplette graf K 3,3 har det største antal spændende træer blandt alle kubiske grafer med det samme antal hjørner [2] .

Wagner -grafen er toppunkttransitiv , men ikke kanttransitiv . Dens fulde automorfi-gruppe er isomorf til den 16. ordens dihedrale gruppe D8 , ottekantssymmetrigruppen , inklusive både rotationer og refleksioner.

Wagner-grafens karakteristiske polynomium er . Dette er den eneste graf, der har et sådant polynomium, som et resultat af hvilket grafen er unikt bestemt af spektret.

Wagner-grafen indeholder ikke trekanter, og dens uafhængige toppunktsæt er tre, hvilket er halvdelen af ​​beviset for, at Ramsey-tallet er R (3,4) (det mindste tal n , således at enhver graf med n toppunkter indeholder enten en trekant eller en uafhængig sæt af fire hjørner) er 9 [3] .

Tæl mindreårige

Möbius-trapper spiller en vigtig rolle i teorien om mindreårige grafer . Det tidligste resultat af denne type er sætningen fra 1937 af Klaus Wagner (en del af en gruppe resultater kendt som Wagners sætning ), om at grafer, der ikke indeholder K 5 mol , kan dannes ved hjælp af klikesummer af plane grafer og M 8 Möbius-stigen [4 ] . Af denne grund kaldes M 8 for Wagner-grafen.

Wagner-grafen er en af ​​de fire minimale forbudte mol til grafer med højst tre træbredder (de andre tre er den komplette K 5 - graf, den regulære oktaedergraf og den femkantede prismegraf ) og en af ​​de fire minimale forbudte mol til grafer med grenbredder højst tre (de tre andre er K 5 , oktaedergrafen og terninggrafen [5] [6] .

Konstruktion

Wagner-grafen er kubisk og Hamiltonsk og har LCF-notationen [4] 8 .

Grafen kan konstrueres som en stige med fire trin på en cyklus af en topologisk Möbius-strimmel .

Galleri

Noter

  1. ↑ JA Bondy, USR Murty. grafteori. - Springer, 2007. - S. 275-276. - ISBN 978-1-84628-969-9 .
  2. ↑ Dmitry Jakobson, Igor Rivin. Om nogle ekstreme problemer i grafteori. – 1999.
  3. ↑ Soif Alexander. Den matematiske malebog. - Springer-Verlag, 2008. - S. 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. Et delvist k -arboret af grafer med afgrænset træbredde // Teoretisk datalogi. - 1998. - T. 209 , udg. 1-2 . — S. 1–45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
  6. ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Grafer med grenbredde højst tre // Journal of Algorithms. - 1999. - T. 32 , no. 2 . — S. 167–194 . - doi : 10.1006/jagm.1999.1011 . .