Arc pancyclicity in multipartite tournaments GTECS – an application in crystallography

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