| Grev Tietze | |
|---|---|
| Opkaldt efter | Heinrich Tietze |
| Toppe | 12 |
| ribben | atten |
| Radius | 3 |
| Diameter | 3 |
| Omkreds | 3 |
| Automorfismer | 12 ( D6 ) |
| Kromatisk tal | 3 |
| Kromatisk indeks | fire |
| Ejendomme |
Cubic Snark |
| Mediefiler på Wikimedia Commons | |
I grafteori er en Tietze-graf en urettet kubisk graf med 12 hjørner og 18 kanter. Grafen er opkaldt efter Heinrich Tietze , som viste i 1910, at en Möbius-strimmel kan opdeles i seks områder, der tangerer hinanden - tre langs kanten af strimlen og tre langs midterlinjen - så seks farver kan være nødvendige for grafer, der kan indlejres i en Möbius-strimmel [ 1] . Grænsesegmenterne af Tietze-domænerne for opdelingen af en Möbius-strimmel (inklusive segmenterne langs kanten af selve strimlen) danner en indlejring af Tietze-grafen.
Tietze-grafen kan fås fra Petersen-grafen ved at erstatte en af dens toppunkter med en trekant [2] . Ligesom Tietze-grafen tjener Petersen-grafen som grænser for seks indbyrdes rørende områder, men i det projektive plan snarere end på Möbius-striben. Hvis vi skærer området ud af et eller andet toppunkt af denne partition af det projektive plan, erstattes toppunktet af dette huls grænser, hvilket giver nøjagtig konstruktionen af Tietze-grafen beskrevet ovenfor.
Både Tietze-grafen og Peterson-grafen er maksimalt ikke-hamiltonske - de har ikke en Hamiltonsk cyklus , men to ikke-tilstødende hjørner kan forbindes med en Hamiltonsk sti [2] . Tietze-grafen og Petersen-grafen er de eneste 2-vertex-forbundne ikke-Hamiltonske kubiske grafer med 12 eller færre hjørner [3] .
I modsætning til Petersen-grafen er Tietze-grafen ikke hypo -hamiltonsk – fjernelse af en af trekantens tre hjørner giver en mindre graf, der forbliver ikke-hamiltonsk.
En kantfarvning af en Tietze-graf kræver fire farver, så dens kromatiske indeks er 4. Det svarer til at sige, at kanterne på en Tietze-graf kan opdeles i fire matchninger , men ikke færre.
Tietze-grafen opfylder en del af kravene til definitionen af en snark - det er en kubisk graf uden broer, og dens kanter kan ikke være 3-farvede. Nogle forfattere begrænser dog snarks til grafer uden 3-cyklusser og 4-cyklusser, og under disse stærkere forhold er Tietze-grafen ikke en snark. Tietze-grafen er isomorf i forhold til grafen J 3 , en graf fra den uendelige familie af "Flower" -snerke foreslået af R. Isaacs i 1975 [4] .
I modsætning til Petersen-grafen kan Tietze-grafen dækkes af fire perfekte matchninger . Denne egenskab spiller en nøglerolle i at bevise, at kontrol af, om en graf kan dækkes af fire matchninger, er et NP-komplet problem [5] .
Tietze-grafen har kromatisk nummer 3, kromatisk indeks 4, omkreds 3 og diameter 3. Dens uafhængighedsnummer er 5, dens automorfigruppe har orden 12 og er isomorf med den dihedrale gruppe D 6 , sekskantens symmetrigruppe , som omfatter både rotationer og refleksioner. Denne gruppe indeholder to baner på størrelse 3 og en på størrelse 6 ved hjørnerne, og derfor er denne graf ikke vertex-transitiv .
Det kromatiske tal på Tietze-grafen er 3.
Det kromatiske indeks for Tietz-grafen er 4.
Tietze-grafen har skæringsnummer 2 og er 1-plan .
Tredimensionel indlejring af Tietze-grafen.