Greve Wagner

Greve Wagner
Döpt efter Klaus Wagner
Toppar åtta
revben 12
Radie 2
Diameter 2
Omkrets fyra
Automorfismer 16 ( D8 )
Kromatiskt nummer 3
Kromatiskt index 3
Egenskaper

kubisk utan Hamiltonska
trianglar vertex-transitiv toroidal



topp
 Mediafiler på Wikimedia Commons

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

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 . .