Cycle Spectra of Graphs
Final Report Abstract
Ziel des Projektes waren Erkenntnisse über das sogenannte Kreisspektrum von Graphen, der Menge der verschiedenen Längen der Kreise eines Graphen. Fragen zum Kreisspektrum von Graphen und insbesondere die Frage nach der Existenz eines Hamiltonkreises gehören zu den klassischen Themen der Graphentheorie. Bereits im Vorläuferprojekt konnten wir eine Reihe schöner Resultate erzielen. Für das hier besprochene Folgeprojekt hatten wir im Antrag insbesondere zwei Themen identifiziert, zu denen wir weitere Fortschritte machen wollten; das Kreisspektrum dünner Hamiltonscher Graphen sowie mehrfarbige Ramsey Resultate für das Kreisspektrum. Zu beiden Themen konnten wir Resultate erzielen. Neben diesen zwei Themen, die direkt aus dem Folgeantrag stammten, sind wir im Verlauf des vergangenen Jahres auf weitere interessante Forschungsfragen zu Kreisen und Kreislängen gestoßen und konnten schöne Resultate erzielen, darunter zur sogenannten Erdös-Pósa Eigenschaft langer Kreise sowie zu Transversalen längster Wege und Kreise und zu Kreislängen in komplementaren Prismen. Die von uns betrachteten Fragen und erzielten Resultate gehören allesamt in den Bereich der mathematischen Grundlagenforschung. Kreise, ihre Längen und ihre effiziente Konstruktion spielen allerdings in vielen Anwendungsfragen eine wichtige Rolle. Das berühmte Traveling Salesman Problem zum Beispiel besteht in der Suche nach einem kürzesten Hamiltonkreis eines kantengewichteten Graphen. Praktisch alle unsere Resultate sind konstruktiv und die entsprechenden Beweise liefern effiziente Algorithmen zur Konstruktion der gesuchten Objekte. Teilweise haben wir algorithmische Fragen auch direkt untersucht.
Publications
-
The Erdös-Pósa Property for Long Circuits, J. Graph Theory
D. Meierling, D. Rautenbach, and T. Sasse
-
Cycle Lengths of Hamiltonian Pℓ-free Graphs. Graphs and Combinatorics, November 2015, Volume 31, Issue 6, pp 2335–2345
D. Meierling and D. Rautenbach
-
Cycles avoiding a Color in Colorful Graphs, J. Graph Theory, Vol 81 Issue 4, April 2016, Pages 342-350
D. Meierling, J. Müttel, and D. Rautenbach
