Hrabě Wagner

Wagnerův graf  je 3- regulární graf s 8 vrcholy a 12 hranami [1] a je to 8-vrcholový Möbiův žebřík .

Vlastnosti

Stejně jako všechny Möbiovy schody není Wagnerův graf rovinný , ale číslo jeho křížení je jedna, takže je apikální . Graf lze vložit bez vlastních průniků na torus nebo projektivní rovinu , takže je toroidní . Jeho obvod je 4, průměr je 2, poloměr je 2, chromatické číslo  je 3, chromatický index  je 3. Graf je spojen vertex-3-connected a edge-3-connected .

Wagnerův graf má 392 kostry . Tento graf a kompletní graf K 3,3 mají největší počet kostry ze všech kubických grafů se stejným počtem vrcholů [2] .

Wagnerův graf je vertex-tranzitivní , ale ne přechodně hranový . Jeho skupina plného automorfismu je izomorfní k dihedrální grupě 16. řádu D8 , skupině symetrie osmiúhelníku , včetně rotací i odrazů.

Charakteristickým polynomem Wagnerova grafu je . Toto je jediný graf, který má takový polynom, v důsledku čehož je graf jednoznačně určen spektrem.

Wagnerův graf neobsahuje trojúhelníky a jeho nezávislá množina vrcholů je tři, což je polovina důkazu, že Ramseyovo číslo je R (3,4) (nejmenší číslo n takové, že každý graf s n vrcholy obsahuje buď trojúhelník, nebo nezávislý množina čtyř vrcholů) je 9 [3] .

Počítat nezletilé

Möbiovy schody hrají důležitou roli v teorii graf minors . Nejčasnějším výsledkem tohoto typu je teorém Klause Wagnera z roku 1937 (součást skupiny výsledků známé jako Wagnerův teorém ), že grafy neobsahující žádné K 5 minority lze vytvořit pomocí klikových součtů rovinných grafů a M 8 Möbiova žebříčku [4]. . Z tohoto důvodu se M 8 nazývá Wagnerův graf.

Wagnerův graf je jedním ze čtyř minimálních zakázaných menších pro grafy se šířkou stromu nejvýše tři (další tři jsou úplný graf K 5 , pravidelný osmistěnný graf a graf pětiúhelníkového hranolu ) a jeden ze čtyř minimálních zakázaných menších pro grafy. s šířkou větví nejvýše tři (další tři jsou K 5 , graf osmistěnu a graf krychle [5] [6] .

Konstrukce

Wagnerův graf je kubický a hamiltonovský a má LCF notaci [4] 8 .

Graf může být konstruován jako žebřík se čtyřmi příčkami na cyklu topologického Möbiova pásu .

Galerie

• Chromatické číslo hraběte Wagnera je 3.

• Chromatický index Wagnerova grafu je 3.

• Wagnerův graf ve formě Möbiova proužku.

Poznámky

1. ↑ JA Bondy, USR Murty. teorie grafů. - Springer, 2007. - S. 275-276. - ISBN 978-1-84628-969-9 .
2. ↑ Dmitrij Jakobson, Igor Rivin. O některých extrémních problémech v teorii grafů. — 1999.
3. ↑ Soif Alexander. Matematická omalovánka. - 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 , čís. 1 . — S. 570–590 . - doi : 10.1007/BF01594196 .
5. ↑ Hans L. Bodlaender. Částečné k -arboretum grafů s omezenou šířkou stromu // Teoretická informatika. - 1998. - T. 209 , vydání. 1–2 . — S. 1–45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
6. ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Grafy s šířkou větve nejvýše tři // Journal of Algorithms. - 1999. - T. 32 , no. 2 . — S. 167–194 . - doi : 10.1006/jagm.1999.1011 . .