Eigenschaften Kubischer Graphen

Kubische Graphen bilden eine der wichtigsten Klassen von Graphen innerhalb der Graphentheorie, da sich viele graphentheoretische Probleme auf kubische Graphen reduzieren lassen. Das Projekt lässt sich in drei Abschnitte unterteilen. Zum Ersten, werden wir neue Snarks erzeugen und ihre Eigenschaften analysieren. Snarks sind zyklisch 4-fach zusammenhängende kubische Graphen, die keine 3-Kantenfärbung zulassen und deren kleinster Kreis mindestens Länge 5 hat. Snarks sind von zentralem Interesse in der Graphentheorie, da sich berühmte Vermutungen auf Snarks reduzieren lassen. Zum Zweiten, werden innerhalb dieses Projektes neue Herangehensweisen bezüglich der folgenden Vermutung angewandt. Dominating Circuit Conjecture (DCC): Jeder zyklisch 4-fach zusammenhängende kubische Graph G besitzt einen Kreis, der von jeder Kante in G mindestens einen Endknoten enthält. Die DCC impliziert, dass G einen Kreis besitzt, der zu jedem Knoten von G höchstens Distanz eins hat. Zum Dritten, werden wir neue und natürliche Fragestellungen bezüglich kubischer Graphen, die eine 3- Kantenfärbung zulassen, untersuchen. Diese Graphen sind daher keine Snarks. Diese Fragestellungen stehen auch im Bezug zu einer der stärksten Versionen der bekannten Circuit Double Cover Conjecture (CDCC). CDCC: Jeder brückenlose Graph G besitzt eine Menge S von Kreisen, sodass jede Kante in G von genau zwei Kreisen aus S überdeckt wird.

Die Cycle Double Cover Conjecture (CDCC) ist eine der zentralen Vermutungen in der Graphentheorie. Sie besagt, dass jeder brückenlose Graph eine Menge von Kreisen hat, so dass jede Kante des Graphen von genau zwei Kreisen der Menge überdeckt wird. Eine solche Menge wird als Cycle Double Cover (CDC) bezeichnet. Die CDCC wurde offiziell in den 1970er Jahren aufgestellt, aber es wird angenommen, dass sie älter ist und aufgrund ihrer Schlichtheit könnte sie tatsächlich viel viel älter sein. In diesem Projekt führten wir neue Beweis Methoden ein und beweisen damit die CDCC für verschiedene interessante Klassen von Graphen. Weiters stellen wir zwei neue Vermutungen auf, die in Verbindung zur CDCC stehen. Snarks sind spezielle kubische Graphen, die nicht 3-Kanten-färbbar sind und eine wesentliche Rolle in vielen zentralen Problemen der Graphentheorie spielen. Es ist zum Beispiel bekannt, dass es genügt die CDCC für Snarks zu beweisen, um die gesamte Vermutung zu beweisen. In diesem Projekt führten wir eine neue Klasse von Snarks ein, sogenannte Hist-Snarks. Diese besitzen eine Zerlegung in einen Spannbaum ohne einen Knoten von Grad 2 (solch ein Spannbaum heißt Hist) und in einen 2-regulären Teilgraphen (bestehend aus den sogenannte äußeren Kreisen). Offensichtlich sind die Knoten der äußeren Kreise die Blätter des Spannbaums. Wir charakterisierten die möglichen auftretenden Längen von äußeren Kreisen von Hist-Snarks. Weiters entdeckten wir, dass jeder Snark mit weniger als 38 Knoten ein Hist-Snark ist und dass es unendlich viele Hist-snarks gibt. Im Bezug zur CDCC bewiesen wir, dass jeder Hist-Snark mit höchstens drei äußeren Kreisen eine CDC hat, die insbesondere alle äußeren Kreise enthält. Zusätzlich beantworteten wir ein offenes Problem über Hists in kubischen Graphen. Es wurde gefragt, ob jeder kubische Graph G eine Hist hat, wenn die cyclic-edge-connectivity von G ausreichend groß ist. Wir zeigten, dass dies nicht zutrifft. Die folgende Vermutung wurde vor einigen Jahren vom Projektleiter aufgestellt: Jeder zusammenhängende kubische Graph hat eine Zerlegung in einen Spannbaum, einen 2-regulären Teilgraphen und in ein Matching. Das Matching kann die leere Menge sein, in diesem Fall ist der Spannbaum ein Hist. Wir bewiesen diese Vermutung für die Klasse alle zusammenhängenden planaren kubischen Graphen. Weiters erzielten wir Fortschritte in der Lösung von Problemen im Zusammenhang von Flüssen, Quadrangulierungen und Kreis Permutations Graphen.