Wagner grafiği - Wagner graph
| Wagner grafiği | |
|---|---|
 Wagner grafiği
| |
| Adını | Klaus Wagner |
| Tepe noktaları | 8 |
| Kenarlar | 12 |
| Yarıçap | 2 |
| Çap | 2 |
| Çevresi | 4 |
| Otomorfizmler | 16 ( D 8 ) |
| Kromatik numara | 3 |
| Kromatik dizin | 3 |
| Cins | 1 |
| Özellikleri |
Kübik Hamilton Üçgeni içermeyen Köşe geçişli Toroidal Apeks |
| Gösterim | M 8 |
| Grafikler ve parametreler tablosu | |
Olarak matematiksel alanında grafik teorisi , Wagner grafik bir 3- normal grafik 8 köşe ve 12 kenarları ile. 8 köşeli Möbius merdiven grafiğidir.
Özellikleri
Bir Möbius merdiveni olarak, Wagner grafiği düzlemsel değildir, ancak bir numaralı kesişme noktasına sahiptir , bu onu bir tepe grafiği yapar . Bir simit veya projektif düzlem üzerinde geçişler olmadan gömülebilir , bu yüzden aynı zamanda toroidal bir grafiktir . Kolan 4, çap 2, yarıçap 2, kromatik sayı 3, kromatik indeks 3'e sahiptir ve hem 3 köşeye hem de 3 kenara bağlıdır .
Wagner grafiğinde 392 uzanan ağaç vardır ; o ve tam grafik K 3,3 , aynı sayıda köşeye sahip tüm kübik grafikler arasında en çok yayılan ağaçlara sahiptir.
Wagner grafiği köşe geçişli bir grafiktir, ancak kenar geçişli değildir . Tam otomorfizm grubu, hem dönüşleri hem de yansımaları içeren bir sekizgenin simetri grubu olan 16. sıradaki dihedral grup D 8'e izomorfiktir .
Karakteristik polinom Wagner grafiğinin olup . Bu karakteristik polinomlu tek grafiktir ve onu spektrumuna göre belirlenen bir grafik yapar.
Wagner grafiktir üçgen içermeyen sahiptir ve bağımsızlık sayısını ispat yarısını sağlayan üç bu Ramsey numarası R (3,4) (en az sayıda N herhangi bir şekilde N -vertex grafiktir, ya bir üçgen ya da dört köşe içerir bağımsız küme) 9'dur.
Grafik küçükleri
Möbius merdivenleri, grafik minör teorisinde önemli bir rol oynar . Bu tür eski sonuç ait 1937 teoremi Klaus Wagner (bilinen bir sonuç kümenin bir parçası Wagner teoremi bir olan grafikler olduğu) K 5 minör kullanılarak oluşturulabilir klik-toplamı düzlemsel grafik ve Möbiüs merdiven birleştirmek için işlemleri M 8 . Bu nedenle M 8'e Wagner grafiği denir.
Wagner grafiği aynı zamanda en fazla üçte (diğer üçü tam grafik K 5 , normal oktahedronun grafiği ve beşgen prizmanın grafiğidir) için en fazla üçte ağaç genişliği grafikleri için dört minimum yasaklanmış küçükten biridir ve dört minimalden biridir. En fazla üç dal genişliği grafikleri için yasaklanmış küçükler (diğer üçü K 5 , oktahedronun grafiği ve küp grafiği ).
İnşaat
Wagner grafiği kübik bir Hamilton grafiğidir ve LCF notasyonu [4] 8 ile tanımlanabilir . Bir bir örneğidir Andrásfai grafik , bir tür circulant grafik noktaların bir döngü içinde düzenlenmiş ve her bir köşe olan pozisyonlar 1 (mod 3) olan bir dizi farklı olan köşe bağlı olduğu. Aynı zamanda dairesel klik K 8/3 ile izomorfiktir .
Topolojik bir Möbius şeridi üzerinde döngüsel yapılmış 4 basamaklı bir merdiven grafiği olarak çizilebilir .
Fotoğraf Galerisi
Renk sayısı Wagner grafiğinin 3'tür.
Renk indeksi Wagner grafiğinin 3'tür.
Möbius şeridinde çizilen Wagner grafiği.
