Veranstaltungen
Veranstaltungen der Fakultät für Mathematik
Aufspannende Wege und Mengen aufspannender Wege in einfach 3-polytopalen Graphen, als obsgua
Termin
09.06.2008, 14.30 Uhr -
Veranstaltungsort
M 1011
Abstract
Die Untersuchung einfach 3-polytopaler Graphen nach Hamiltonkreisen
ist aus historischen Gründen (Vierfarbenproblem, Taitsche Vermutung) mit
Nachdruck betrieben worden. Von besonderem Interesse war hierbei die
Frage, mit bis zu wievielen Punkte ein solcher Graph auf jeden Fall einen
Hamiltonkreis enthält. Diese Frage konnte 1988 abschließend beantwortet
werden.
Man kann die Fragestellung so abändern, dass man statt eines Kreises einen anderen aufspannenden Teilgraphen wählt, z. B. einen Weg, eine Vereinigung von Kreisen oder Wegen oder einen n-Weg (d. h. eine disjunkte Vereinigung von bis zu n Wegen.) Für jeden dieser Fälle werden Graphen konstruiert, die den entsprechenden aufspannenden Teilgraphen nicht enthalten.
Zur Konstruktion dieser Graphen sind bestimmte Teilgraphen (sog. 3- Stücke) erforderlich. Auch auf diese Teilgraphen und ihre Minimalität wird näher eingegangen.
Der letzte Abschnitt gilt der Fragestellung, mit bis zu wievielen Punkten ein einfach 3-polytopaler Graph nachgewiesenermaßen einen aufspannenden Weg enthält. Im Gegensatz zur analogen Untersuchung von Hamiltonkreisen wurde dieses Thema bislang wenig untersucht und ist weit von einer abschließenden Antwort entfernt.
Man kann die Fragestellung so abändern, dass man statt eines Kreises einen anderen aufspannenden Teilgraphen wählt, z. B. einen Weg, eine Vereinigung von Kreisen oder Wegen oder einen n-Weg (d. h. eine disjunkte Vereinigung von bis zu n Wegen.) Für jeden dieser Fälle werden Graphen konstruiert, die den entsprechenden aufspannenden Teilgraphen nicht enthalten.
Zur Konstruktion dieser Graphen sind bestimmte Teilgraphen (sog. 3- Stücke) erforderlich. Auch auf diese Teilgraphen und ihre Minimalität wird näher eingegangen.
Der letzte Abschnitt gilt der Fragestellung, mit bis zu wievielen Punkten ein einfach 3-polytopaler Graph nachgewiesenermaßen einen aufspannenden Weg enthält. Im Gegensatz zur analogen Untersuchung von Hamiltonkreisen wurde dieses Thema bislang wenig untersucht und ist weit von einer abschließenden Antwort entfernt.
Vortragende(r)
Peter Knorr
Herkunft der/des Vortragenden
Fakultät für Mathematik, TU Dortmund