Generalized tournaments and efficient orientations of graphs

• Verallgemeinerte Turniere und effiziente Orientierungen von Graphen

Surmacs, Michel; Guo, Yubao (Thesis advisor); Triesch, Eberhard (Thesis advisor)

Aachen (2021)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2021

Abstract

This thesis is concerned with both theoretical structural results whose possible applications are yet to be determined and algorithmic solutions to mathematical models inspired by real-world problems. In Part I, generalizations of tournaments - i.e., orientations of complete graphs - are studied. We begin with a short survey on already established results on tournaments, as well as on semicomplete digraphs, of which we then proceed to present new generalized versions. We are particularly interested in the extension of certain structural results on tournaments concerning paths and cycles. In multipartite tournaments, for example, we consider two competing concepts of quasi-length and particularly, their implications on pancyclicity, as well as Hamiltonicity in those digraphs. Furthermore, we introduce the class of minimum quasi-pancyclic c-partite tournaments - i.e., c-partite tournaments that contain exactly c quasi-pancyclic vertices - prove the long standing conjecture that these c vertices induce a strong subtournament, and give further structural results that culminate in a characterization of all minimum quasi-pancyclic 3-partite tournaments and closely related classes of digraphs. We then leave the realm of directed graphs to analyse hypertournaments, an extension of tournaments to the field of directed hypergraphs. Among other results, we prove that strong hypertournaments are vertex-pancyclic and contain a vertex whose all out-arcs are pancyclic. We introduce distinct possibilities to define regularity in hypertournaments, study necessary and sufficient conditions for which regular hypertournaments exist, and construct some explicit examples. Finally, we prove that regular hypertournaments, in contrast to their general strong counterparts, are arc-pancyclic. Part II of this thesis then builds a bridge between undirected and directed graphs. Based on an undirected graph, we study efficient ways to construct a corresponding orientation. As most of our results provide linear or polynomial algorithms to produce the discussed orientations, in contrast to Part I, Part II displays a stronger emphasis on application. We focus on the oriented diameter of an undirected graph as a measure of efficiency. Since its exact determination is proven to be NP-complete, we present new upper bounds on the oriented diameter in terms of a selection of graph parameters (e.g., the minimum and the maximum degree) as well as for certain classes of graphs (e.g., maximal outerplanar graphs, chordal maximal planar graphs, and complete Apollonian networks). Our bounds are mostly proven to be best possible except possibly for a small additive constant.