Detailansicht
Konsistente Kreise in Graphen
Julia Wessely
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Lehramtsstudium UF Mathematik UF Informatik und Informatikmanagement
Betreuer*in
Bernhard Krön
DOI
10.25365/thesis.43127
URN
urn:nbn:at:at-ubw:1-24229.92895.477054-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Konsistente Kreise in endlichen Graphen wurden 1971 von J.H. Conway eingeführt. Ein Kreis wird konsistent unter der Aktion einer Automorphismengruppe genannt, wenn es ein Gruppenelement gibt, das den Kreis um einen Schritt rotiert. Er zeigte, dass die Anzahl der Orbits nichttrivialer konsistenter Kreise in einem endlichen Graphen um eins weniger als der Knotengrad des Graphen ist, wenn eine Untergruppe der vollen Automorphismengruppe bogentransitiv auf dem Graphen agiert. In der vorliegenden Diplomarbeit wird dieses Resultat von Conway auf unendliche Graphen und Automorphismengruppen, die knotentransitiv auf endlichen und unendlichen Graphen agieren, verallgemeinert. In unendlichen Graphen betrachten wir auch Doppelstrahlen als Kreise und definieren die Vielfachheit für Orbits konsistenter Kreise. Wir zeigen, dass die Summe der Vielfachheiten von Orbits konsistenter Kreise gleich dem Knotengrad des Graphen ist. Weiters zeigen wir, dass für diese Behauptung die Automorphismengruppe, die auf dem Graphen agiert, in der vollen Automorphismengruppe abgeschlossen sein muss. Hierfür betrachten wir Automorphismengruppen als topologische Gruppen bezüglich der Topologie der punktweisen Konvergenz. Für den Beweis unseres Hauptsatzes verwenden wir die Idee von Biggs und Conway, einen Symmetriebaum zu definieren, der alle Infomationen über die Struktur der Kongruenzklassen konsistenter Kreise eines gegebenen Graphen und einer gegebenen Automorphismengruppe enthält. Wir zeigen die bijektive Korrespondenz zwischen den maximalen Wegen im Baum und den Kongruenzklassen konsistenter Kreise im Graphen. In einem weiteren Kapitel diskutieren wir unser Resultat im Diestel-Leader-Graphen.
Abstract
(Englisch)
Consistent cycles in finite Graphs were introduced by J.H. Conway in 1971. He observed that if a subgroup G of the full automorphism group of a graph acts arc-transitively on it, then the number of orbits of non-trivial consistent cycles under the action of the group G on the graph is one less than the valence of the graph. A cycle is called consistent under a group of automorphisms G acting on the graph if there exists an element rotating the cycle by one step. In this diploma thesis we generalize this result of Conway to infinite graphs and groups of automorphisms acting vertex-transitively on finite and infinite graphs. In infinite graphs we also consider double-rays as cycles and define the multiplicity of orbits of consistent cycles. We state that the sum of multiplicities of orbits of consistent cycles is equal to the degree of the graph. Further we show for this conjecture that the automorphism group acting on a graph has to be closed in the full automorphism group. Therefor we consider groups of automorphisms as topological groups with the topology of point-wise convergence. For the proof of our main theorem we use Biggs' and Conway's idea of defining a symmetry tree that encodes all the information about the structure of congruence classes of consistent cycles in a given graph and for a given group of automorphisms. We show the bijective correspondence between the maximal walks in the tree and the congruence classes of consistent cycles in the graph. In a further section we discuss our results in the Diestel-Leader graph.
Schlagwörter
Schlagwörter
(Englisch)
Graph theory automorphisms transitive graphs infinite graphs
Schlagwörter
(Deutsch)
Graphentheorie Automorphismen transitive Graphen unendliche Graphen
Autor*innen
Julia Wessely
Haupttitel (Deutsch)
Konsistente Kreise in Graphen
Paralleltitel (Englisch)
Consistent cycles in graphs
Publikationsjahr
2016
Umfangsangabe
viii, 60 Seiten : Illustrationen
Sprache
Deutsch
Beurteiler*in
Bernhard Krön
Klassifikation
31 Mathematik > 31.12 Kombinatorik, Graphentheorie
AC Nummer
AC13345399
Utheses ID
38166
Studienkennzahl
UA | 190 | 406 | 884 |