| Greve Tietze | |
|---|---|
| Döpt efter | Heinrich Tietze |
| Toppar | 12 |
| revben | arton |
| Radie | 3 |
| Diameter | 3 |
| Omkrets | 3 |
| Automorfismer | 12 ( D6 ) |
| Kromatiskt nummer | 3 |
| Kromatiskt index | fyra |
| Egenskaper |
Cubic Snark |
| Mediafiler på Wikimedia Commons | |
I grafteorin är en Tietze-graf en oriktad kubisk graf med 12 hörn och 18 kanter. Grafen är uppkallad efter Heinrich Tietze , som 1910 visade att en Möbiusremsa kan delas in i sex regioner som tangerar varandra – tre längs kanten av remsan och tre längs mittlinjen – så sex färger kan behövas för grafer som kan bäddas in i en Möbiusremsa [ 1] . Gränssegmenten för Tietze-domänerna för uppdelningen av en Möbiusremsa (inklusive segmenten längs gränsen till själva remsan) bildar en inbäddning av Tietze-grafen.
Tietze-grafen kan erhållas från Petersen-grafen genom att ersätta en av dess hörn med en triangel [2] . Liksom Tietze-grafen fungerar Petersen-grafen som gränser för sex regioner som berör varandra, men i det projektiva planet , snarare än på Möbius-remsan. Om vi skär ut grannskapet till någon vertex av denna partition av det projektiva planet, ersätts vertexen av gränserna för detta hål, vilket ger exakt konstruktionen av Tietze-grafen som beskrivs ovan.
Både Tietze-grafen och Peterson-grafen är maximalt icke-hamiltonska - de har inte en Hamiltonsk cykel , men vilka två icke-angränsande hörn som helst kan kopplas samman med en Hamiltonsk bana [2] . Tietze-grafen och Petersen-grafen är de enda 2-vertex-anslutna icke-Hamiltonska kubiska graferna med 12 eller färre hörn [3] .
Till skillnad från Petersen-grafen är Tietze-grafen inte hypo -hamiltonsk – om man tar bort en av triangelns tre hörn får man en mindre graf som förblir icke-hamiltonsk.
En kantfärgning av en Tietze-graf kräver fyra färger, så dess kromatiska index är 4. Detta motsvarar att säga att kanterna på en Tietze-graf kan delas in i fyra matchningar , men inte mindre.
Tietze-grafen uppfyller en del av kraven för definitionen av en snark - det är en kubisk graf utan broar och dess kanter kan inte vara 3-färgade. Vissa författare begränsar dock snarks till grafer utan 3-cykler och 4-cykler, och under dessa starkare förhållanden är Tietze-grafen inte en snark. Tietze-grafen är isomorfisk mot grafen J 3 , en graf från den oändliga familjen av "Flower" -snärkar som föreslogs av R. Isaacs 1975 [4] .
Till skillnad från Petersen-grafen kan Tietze-grafen täckas av fyra perfekta matchningar . Denna egenskap spelar en nyckelroll för att bevisa att kontroll av om en graf kan täckas av fyra matchningar är ett NP-komplett problem [5] .
Tietze-grafen har kromatiskt nummer 3, kromatiskt index 4, omkrets 3 och diameter 3. Dess oberoende nummer är 5, dess automorfismgrupp har ordning 12 och är isomorf till den dihedriska gruppen D 6 , hexagonens symmetrigrupp , som inkluderar både rotationer och reflektioner. Denna grupp innehåller två banor av storlek 3 och en av storlek 6 vid hörnen, och därför är denna graf inte vertextransitiv .
Det kromatiska numret på Tietze-grafen är 3.
Det kromatiska indexet för Tietz-grafen är 4.
Tietze-grafen har skärningspunkt nummer 2 och är 1-plan .
Tredimensionell inbäddning av Tietze-grafen.