Arc pancyclicity in multipartite tournaments  GTECS – an application in crystallography

Grüter, Steffen; Triesch, Eberhard; Guo, Yubao

doi:5301

Arc pancyclicity in multipartite tournaments GTECS – an application in crystallography = Bogen-Panzyklizität in multipartiten Turnieren & GTECS – eine Anwendung in der Kristallographie

Grüter, Steffen

2014

VerantwortlichkeitsangabeSteffen Grüter

ImpressumAachen : Shaker 2014

UmfangX, 128 S. : Ill., graph. Darst.

ReiheBerichte aus der Mathematik

Zugl.: Aachen, Techn. Hochsch., Diss., 2014

Zweitveröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Guo, Yubao (Thesis advisor) ; Triesch, Eberhard (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2014-07-25

Online
URN: urn:nbn:de:hbz:82-opus-53017
URL: https://publications.rwth-aachen.de/record/459818/files/5301.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Graphentheorie (Genormte SW) ; Kristallographie (Genormte SW) ; Mathematik (frei) ; multipartite Turniere (frei) ; periodische Graphen (frei) ; graph theory (frei) ; multipartite tournaments (frei) ; periodic graphs (frei) ; crystallography (frei)

Thematische Einordnung (Klassifikation)
DDC: 510
msc: 05C20 * 05C90

Kurzfassung
Die vorliegende Arbeit besteht aus zwei Teilen wobei sich der erste Teil mit den Bereichen Bogen-Panzyklizität und Zusammenhang in multipartiten Turnieren beschäftigt und der zweite Teil die Ideen und Algorithmen hinter dem Programm GTECS, einem neuen Hilfsmittel zur Analyse ausgedehnter Strukturen im Bereich der Kristallographie, erläutert. Kapitel 2 aus Teil I befasst sich mit dem Studium t-panzyklischer Bogen in stark zusammenhängenden Turnieren T, t = 3,...,|V(T)|. Insbesondere betrachten wir die maximale Anzahl t-panzyklischer Bogen auf einem Hamiltonkreis in T - bezeichnet mit h^t(T) - und die Anzahl aller t-panzyklischer Bogen in T, bezeichnet mit p^t(T). Wir verallgemeinern einen Satz von Moon, indem wir h^t(T) nach unten beschränkt durch t, t = 3,...,|V(T)|, für alle stark zusammenhängenden Turniere zeigen, und charakterisieren schließlich alle Turniere T, für die h^t(T) = t, p^t(T) = t, h^t(T) = t+1 oder p^t(T) = t+1 mit t größer oder gleich 4 gilt. Kapitel 3 präsentiert ein erstes Ergebnis zum Thema Aus-Bogen-Panzyklizität in multipartiten Turnieren. Während für stark zusammenhängende Turniere schon die Existenz einer Ecke, deren Aus-Bogen alle panzyklisch sind, gezeigt wurde, geben wir verschiedene Herangehensweisen für diese Fragestellung in multipartiten Turnieren an. Einer dieser Ansätze führt zu einem im Allgemeinen bestmöglichen Resultat für 2-fach stark zusammenhängende multipartite Turniere. Kapitel 4 beschäftigt sich mit Digraphen im Allgemeinen. Wir übertragen das Konzept von Baumspannern in zusammenhängenden Graphen auf zusammenhängende Digraphen indem wir Paare von Baumspannern einführen. Damit erweitern wir Aussagen über die Existenz spezieller additiver (Baum-)Spanner für die Klasse der (alpha, r)-zerlegbaren Graphen auf den gerichteten Fall. Teil II dieser Arbeit stellt zunächst die Idee hinter GTECS, einem interdisziplinären Projekt aus den Bereichen Chemie, Informatik und Mathematik, vor und begründet insbesondere die Notwendigkeit eines entsprechenden Analyse-Tools für die Untersuchung ausgedehnter Kristallstrukturen. Nach einer Einführung in periodische Graphen, die zur Modellierung verwendet werden, werden verschiedene Algorithmen zur Vereinfachung der Strukturen vorgestellt. Kapitel 7 enthält dabei den Hauptalgorithmus, welcher Informationen über Periodizität und Anzahl der Komponenten einer Struktur zur Verfügung stellt. Abschließend werden mehrere topologische Symbole als wichtige Charakterisierungsmittel einzelner Strukturen sowie Algorithmen zu deren Berechnung präsentiert.

This thesis consists of two parts where the first one represents theoretical results in the field of arc-pancyclicity and connectivity in multipartite tournaments and the second part presents the graph theoretical ideas and algorithms behind the recently developed software GTECS which is a tool for analysing large structures in crystallography. In Chapter 2 of Part I we study t-pancyclic arcs in strong tournaments T for all t = 3,...,|V(T)|. In particular, we consider the maximum number of t-pancyclic arcs on a Hamiltonian cycle of T denoted by h^t(T) and the number of all such arcs in T denoted by p^t(T). In this context, we generalise a theorem due to Moon by showing that h^t(T) is lower bounded by t, t = 3,...,|V(T)|, for all strong tournaments. Additionally, we characterise all tournaments T with h^t(T) = t, p^t(T) = t, h^t(T) = t+1 and p^t(T) = t+1, t greater or equal 4. In Chapter 3 we present a first result on out-arc-pancyclicity in multipartite tournaments. While for a strong tournament the existence of a vertex whose all out-arcs are pancyclic has been shown, we give different approaches for a corresponding generalisation. Using one of these approaches, we finally present a similar result for 2-strong multipartite tournaments and show that it is best possible in general. In Chapter 4 we consider digraphs in general and transfer the concept of tree spanners in connected graphs to connected digraphs by introducing pairs of tree spanners. In this context, we adapt results concerning the existence of special additive (tree) spanners in the class of (alpha, r)-decomposable graphs to the equivalent directed case. Part II of this thesis including the Chapters 5 to 8 starts with an introduction of GTECS, which is the result of an interdisciplinary project of chemists, computer scientists and mathematicians. We show the necessity of such a tool for the analysis of extended crystal structures and introduce the concept of representing such structures by periodic graphs. Depending on this graph class, we introduce various algorithms to simplify the given structure by keeping its topology using for example path- or cycle-contraction. While the main algorithm gives valuable information about the periodicity and the number of components of such a structure, we conclude with a chapter on topological symbols which are important measurements for comparing different structures and show how they are calculated in GTECS.

OpenAccess:
PDF