Kreise in Graphen und Eigenschaften von Graphen mit speziellen Kreisstrukturen

Das Projekt betrachtet drei graphentheoretische Forschungsthemen, die zu einem wesentlichen Teil auch mit algorithmischen Methoden und entsprechenden Implementierungen behandelt werden. Diese Forschungsrichtungen sind: (a) Hamiltonsche Kreise in speziellen Graphenklassen, (b) Probleme bezüglich (Doppel-)Überdeckungen mit Kreisen sowie (c) die Unabhängigkeitszahl für spezielle Graphenklassen. Bezüglich Hamiltonsche Kreise wollen wir die allgemeinstmögliche Block-Artikulations-Struktur eines Graphen G bestimmen, sodass G^2 hamiltonsch ist. Weiters wollen wir uns auch mit Aspekten und gewissen Verallgemeinerungen der Barnette`schen Vermutung beschäftigen, wonach ebene, kubische, bipartite 3fach-zusammenhängende Graphen hamiltonsch sind. Schließlich soll das Problem der Konstruktion eindeutig hamiltonscher planarer Graphen betrachtet werden. Bezüglich Kreisüberdeckungen beabsichtigen wir, neue Graphenklassen zu finden, in denen die Kreis- Doppelüberdeckungs-Vermutung (CDCC) gilt. Sabidussi`s Kompatibilitäts-Vermutung (SCC) ist mit der CDCC eng verwandt, sodass wir die SCC für gewisse Typen eulerscher Graphen beweisen wollen. Eine andere Herangehensweise zur Lösung der CDCC besteht darin, zwei disjunkte bipartisierende Matchings (BMs) bezüglich eines dominierenden Kreises (DC) zu finden; deshalb wollen wir Snarks mit einem stabilen dominierenden Kreis bezüglich der Existenz zweier disjunkter BMs testen. In einem geringeren Maße wollen wir auch das Kreis-Überdeckungsproblem mit minimalen Kosten in nicht- planaren Graphen behandeln und dabei verschiedene Computermethoden anwenden. Schließlich beabsichtigen wir, das Unabhängigkeitsverhältnis in solchen 4-regulären Graphen zu bestimmen, die in einen hamiltonschen Kreis H und einen quadratischen Faktor zerlegt werden können, dessen Kreise konform in H eingeschrieben sind. Neben theoretischer Grundlagenforschung werden auch Computer-Algorithmen und Techniken der kombinatorischen Optimierung und Problemlösung eine wichtige Rolle spielen. In mehreren Fällen wird die Entwicklung von Algorithmen und deren Implementierung von den im Rahmen dieses Projekts erzielten theoretischen Resultaten abhängen.

Graphentheorie ist ein Zweig der Diskreten Mathematik und spielt eine wichtige Rolle in verschiedenen Wissenschaften wie z.B. in der Unternehmensforschung, den Sozialwissenschaften, theoretischer Chemie, und in anderen Gebieten. Graphen sind abstrakte Objekte bestehend aus Knoten und Kanten, die in der Ebene als Punkte und Linien, die Paare von Punkten verbinden, gezeichnet werden können. Die Durchlaufung von Graphen, Zerlegung und Überdeckung von Graphen, unabhängige Knotenmengen in Graphen, um nur einige zu nennen, sind zentrale Forschungsthemen in der Graphentheorie. Bei hamiltonschen Kreisen bzw. Wegen wird jeder Knoten genau einmal aufgesucht und man endet wieder am Ausgangsknoten bzw. in einem anderen Knoten. Das Projekt behandelte hamiltonschen Kreise/Wege a) im Quadrat G2, das man aus einem Graphen G erhält, indem man zu G je zwei nicht-adjazente Knoten x und y durch eine Kante verbindet, falls jene einen gemeinsamen Nachbar haben. Es wurden bestmögliche Resultate bzgl. Hamiltonscher Kreise/Wege in G2 erzielt, falls G nicht separabel ist (d.h., Weglassen eines beliebigen Knoten lässt den Rest zusammenhängend). Diese Resultate sind die Basis für eine Beschreibung der allgemeinst-möglichen Struktur eines Graphen, so daß das Quadrat einen hamiltonschen Kreis besitzt; b) in Polyeder-Graphen, in denen jede Fläche eine gerade Anzahl von Ecken enthält und jede Ecke drei Flächen angehört. Für solche Graphen behauptet die Barnette'sche Vermutung die Existenz eines hamiltonschen Kreises. Bis dato beste Teillösungen dieser Vermutung wurden gefunden. Eulersche Graphen, wo jeder Knoten zu einer geraden Anzahl von Kanten inzident ist, haben eine Kreiszerlegung (jede Kante gehört genau einem Kreis der Zerlegung an). Will man auch dann eine Kreiszerlegung erzielen, wenn gewisse Durchgänge verboten sind, so spricht man von einer kompatiblen Kreiszerlegung. Dazu wurde ein ziemlich allgemeiner Satz erzielt, der zu einer direkten Anwendung auf die Cycle Double Cover Conjecture (CDCC) führt, wonach jeder brückenlose Graph (jede Kante gehört einem Kreis an) eine Familie S von Kreisen enthält, so dass jede Kante genau 2 Elementen von S angehört. Weitere Teillösungen der CDCC, in denen von gewissen Teilgraphen eines gegebenen brückenlosen Graphen ausgegangen wird, wurden erzielt. Eine Menge S von Knoten im Graphen G heißt unabhängig, wenn keine zwei Knoten in S durch eine Kante verbunden sind. Ein Graph heißt glatt, wenn er 4-regulär ist und in einen hamiltonschen Kreis und darin eingeschriebene sich selbst nicht überschneidende Kreise zerlegt werden kann. Es wird vermutet, dass jeder hinreichend große glatte Graph mit n Knoten eine unabhängige Knotenmenge mit mindestens 2n/7 Knoten enthält. Verschiedene Teillösungen dieser Vermutung wurden erzielt. Zusätzlich zu den theoretischen Ergebnissen wurden auch computerbasierte Verfahren entwickelt und verwendet, um konkrete Graphen mit entsprechenden Strukturen zu finden oder deren Nichtexistenz bis zu einer bestimmten Größe nachzweisen.