Detailansicht
Consistent cycles in Graphs
Julia Wessely
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Bernhard Krön
DOI
10.25365/thesis.22210
URN
urn:nbn:at:at-ubw:1-29743.92607.331559-6
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. Er behauptete, dass die Anzahl der Orbits nicht trivialer 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. Ein Kreis wird konsistent unter der Aktion einer Automorphismengruppe genannt, wenn es ein Gruppenelement gibt, das den Kreis um einen Schritt rotiert. 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 von konsistenten Kreisen. Wir behaupten, dass die Summe der Vielfachheiten der Orbits von konsistenten Kreisen 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 Symmetrie Baum zu definieren, der alle Informationen über die Struktur der Kongruenzklassen von konsistenten Kreisen eines gegebenen Graphen und einer gegebenen Automorphismengruppe enthält. Wir zeigen die bijektive Korrespondenz zwischen den maximalen Wegen im Baum und den Kongruenzklassen von konsistenten Kreisen im Graphen.
Abstract
(Englisch)
Consistent cycles in finite Graphs were introduced by J.H. Conway in 1971. He observed that if a subgroup 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 on the graph is one less than the valence of the graph. A cycle is called consistent under a group of automorphisms 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.
Schlagwörter
Schlagwörter
(Englisch)
graphs transitive infinite consistent cycles
Schlagwörter
(Deutsch)
Graphen transitiv unendlich konsistente Kreise
Autor*innen
Julia Wessely
Haupttitel (Englisch)
Consistent cycles in Graphs
Paralleltitel (Deutsch)
Konsistente Kreise in Graphen
Publikationsjahr
2012
Umfangsangabe
53 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Bernhard Krön
Klassifikation
31 Mathematik > 31.12 Kombinatorik, Graphentheorie
AC Nummer
AC11005506
Utheses ID
19837
Studienkennzahl
UA | 405 | | |