Greve Wagner

Wagner-grafen  är en 3- regelbunden graf med 8 hörn och 12 kanter [1] och är en Möbius-stege med 8 hörn .

Egenskaper

Som alla Möbiustrappor är Wagner-grafen inte plan , men dess korsningsnummer är ett, vilket gör den apikal . En graf kan bäddas in utan självkorsningar på ett torus eller projektivt plan , så att den är toroidformad . Dess omkrets är 4, diameter är 2, radie är 2, kromatiskt tal  är 3, kromatiskt index  är 3. Grafen är både vertex-3-ansluten och kant-3-ansluten .

Wagner-grafen har 392 spännande träd . Denna graf och hela grafen K 3,3 har det största antalet spännande träd bland alla kubiska grafer med samma antal hörn [2] .

Wagner-grafen är vertextransitiv , men inte kanttransitiv . Dess fullständiga automorfismgrupp är isomorf till den 16:e ordningens dihedriska grupp D8 , oktagonsymmetrigruppen , inklusive både rotationer och reflektioner.

Det karakteristiska polynomet i Wagnergrafen är . Detta är den enda grafen som har ett sådant polynom, som ett resultat av vilket grafen bestäms unikt av spektrumet.

Wagner-grafen innehåller inga trianglar och dess oberoende vertexuppsättning är tre, vilket är hälften av beviset på att Ramsey-talet är R (3,4) (det minsta talet n så att varje graf med n hörn innehåller antingen en triangel eller en oberoende uppsättning av fyra hörn) är 9 [3] .

Räkna minderåriga

Möbiustrappor spelar en viktig roll i teorin om graph minors . Det tidigaste resultatet av denna typ är satsen från 1937 av Klaus Wagner (en del av en grupp resultat som kallas Wagners sats ) om att grafer som inte innehåller några K 5 -moll kan bildas med hjälp av klicksummor av plana grafer och M 8 Möbius-stegen [4 ] . Av denna anledning kallas M 8 för Wagner-grafen.

Wagner-grafen är en av de fyra minimala förbjudna minorerna för grafer med högst tre trädbredder (de andra tre är den kompletta K 5 -grafen, den vanliga oktaedergrafen och den femkantiga prismagrafen ) och en av de fyra minimala förbjudna molltalen för grafer med grenbredder som högst tre (de andra tre är K 5 , oktaedergrafen och kubgrafen [5] [6] .

Byggnad

Wagner-grafen är kubisk och Hamiltonsk och har LCF-notationen [4] 8 .

Grafen kan konstrueras som en stege med fyra steg på en cykel av en topologisk Möbiusremsa .

Galleri

• Greve Wagners kromatiska nummer är 3.

• Det kromatiska indexet för Wagner-grafen är 3.

• Wagnergraf i form av en Möbiusremsa.

Anteckningar

1. ↑ JA Bondy, USR Murty. grafteori. - Springer, 2007. - S. 275-276. - ISBN 978-1-84628-969-9 .
2. ↑ Dmitry Jakobson, Igor Rivin. Om några extrema problem inom grafteorin. — 1999.
3. ↑ Soif Alexander. Den matematiska målarboken. - 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. Ett partiellt k -arboretum av grafer med avgränsad trädbredd // Teoretisk datavetenskap. - 1998. - T. 209 , nummer. 1–2 . — S. 1–45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
6. ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Grafer med högst tre grenbredd // Journal of Algorithms. - 1999. - T. 32 , nr. 2 . — S. 167–194 . - doi : 10.1006/jagm.1999.1011 . .