Local tournaments and in-tournaments

Meierling, Dirk; Volkmann, Lutz

doi:28143

Local tournaments and in-tournaments = Lokale Turniere und In-Turniere

Meierling, Dirk (Author)

2007

Verantwortlichkeitsangabevorgelegt von Dirk Meierling

ImpressumAachen : Publikationsserver der RWTH Aachen University 2007

UmfangXII, 160 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2007

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Volkmann, Lutz (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2007-11-28

Online
URN: urn:nbn:de:hbz:82-opus-21199
URL: https://publications.rwth-aachen.de/record/62595/files/Meierling_Dirk.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Turnier <Mathematik> (Genormte SW) ; Mathematik (frei) ; graph theory (frei) ; digraph (frei) ; local tournament (frei) ; in-tournament (frei)

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

Kurzfassung
Ein Digraph ohne Schlingen, parallele Bogen und Kreise der Länge zwei, heisst lokales Turnier, falls sowohl die negative als auch die positive Nachbarschaft jeder Ecke ein Turnier induziert. Diese Klasse kann weiter zur Klasse der In-Turniere verallgemeinert werden, indem man nur fordert, dass Ecken, die gemeinsame positive Nachbarn haben, adjazent sind. Lokale Turniere und In-Turniere sind also Verallgemeinerungen von Turnieren dergestalt, dass die globale Adjazenz von Ecken auf Eckenpaare übertragen wird, die eine lokale Eigenschaft gemein haben. In dieser Arbeit untersuchen wir die Weg- und Kreisstruktur von lokalen Turnieren und In-Turnieren, sowie das verwandte Thema der Eckenlöschung. In Kapitel 1 werden die benötigte Terminologie und Notationen, sowie die grundlegenden Eigenschaften lokaler Turniere und In-Turniere eingeführt. Der verbleibende Teil der Arbeit ist in drei Teile unterteilt. Im ersten Teil, der aus den Kapiteln 2 bis 4 besteht, untersuchen wir die Wegstruktur lokaler Turniere und In-Turniere. In Kapitel 2 entwickeln wir die Struktur lokaler Turniere, die einen Bogen haben, der nicht auf einem Hamiltonweg liegt. Mithilfe dieser Struktur können wir zahlreiche hinreichende Kriterien dafür angeben, dass jeder Bogen eines lokalen Turniers auf einem Hamiltonweg liegt. Diese Resultate verallgemeinern Ergebnisse von Busch und Busch, Jacobson und Reid für Turniere. In den folgenden beiden Kapiteln konzentrieren wir uns auf Wege kürzerer Länge. Wir beweisen eine Vermutung von Volkmann und beschäftigen uns mit Varianten von Volkmanns Problemstellung. Der zweite Teil dieser Dissertation besteht aus zwei Kapiteln, in denen wir folgendes Problem untersuchen: wie viele nicht-kritische Ecken hat ein stark zusammenhängendes lokales Turnier oder In-Turnier in Abhängigkeit vom minimalen Eckengrad? In Kapitel 5 verallgemeinern wir Ergebnisse von Kotani für Turniere und von Meierling und Volkmann für lokale Turniere. In Kapitel 6 betrachten wir das Problem der Eckenlöschung, d.h. wir untersuchen, ob ein stark zusammenhängendes lokales Turnier zwei verschiedene Ecken hat, deren Löschung den starken Zusammenhang des lokalen Turniers nicht zerstört. Wir charakterisieren alle lokalen Turniere mit genau zwei solchen Ecken und verallgemeinern dadurch ein Ergebnis von Las Vergnas für Turniere. Der dritte Teil dieser Arbeit ist der Kreisstruktur lokaler Turniere und In-Turniere gewidmet. Indem wir die Ergebnisse der vorherigen Kapitels umformulieren, können wir alle lokalen Turniere mit genau zwei Kreisen der Länge Ordnung minus eins charakterisieren. Mithilfe eines speziellen Parameters, der quasi-Taillenweite eines lokalen Turniers, untersuchen wir in Kapitel 7, wie viele Kreise gegebener Länge ein stark zusammenhängendes lokales Turnier mindestens hat. Für Turniere wurde dieses Problem bereits von Moon und Las Vergnas untersucht und vollständig gelöst. Unsere Ergebnisse verallgemeinern die Resultate von Las Vergnas. In Kapitel 8 untersuchen wir das interessante Problem, unter welchen Voraussetzungen ein stark zusammenhängendes lokales Turnier zwei komplementäre Kreise hat. Bereits 1996 haben Guo und Volkmann alle zweifach stark zusammenhängenden lokalen Turniere charakterisiert, die nicht kreiskomplementär sind. Dieses Ergebnis wurde auf verschiedene Weisen verallgemeinert. Zum Beispiel haben Meierling und Volkmann alle zweifach stark zusammenhängenden In-Turniere ohne komplementäre Kreise charakterisiert. In diesem Kapitel untersuchen wir die Struktur stark, aber nicht zweifach stark, zusammenhängender lokaler Turniere, die nicht kreiskomplementär sind. Als Anwendung unserer Ergebnisse können wir eine hinreichende Bedingung dafür angeben, dass ein lokales Turnier einen k-Kreis-Faktor hat. Unser Resultat verallgemeinert Ergebnisse von Li und Shu für Turniere. Im letzten Kapitel untersuchen wir erweiterbare Kreise in stark zusammenhängenden In-Turnieren. Diese Eigenschaft wurde 1989 von Hendry für Digraphen im allgemeinen eingeführt. Tewes und Volkmann haben bereits In-Turniere mit dieser Eigenschaft untersucht und eine Vermutung formuliert, die wir hier beweisen.

A digraph without loops, multiple arcs and cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. In claiming adjacency only for vertices that have a common out-neighbor, this class can be further generalized to the class of in-tournaments. Hence local tournaments and in-tournaments are generalizations of tournaments in such a way that the general adjacency of vertices is transferred to only those pairs of vertices that share a local property. In this thesis we study the path and cycle structure of local tournaments and in-tournaments and the related topic of vertex deletion. The required terminology and notation as well as the basic structural properties of local tournaments and in-tournaments are established in Chapter 1. The remaining part of this thesis is subdivided in three parts. In the first part consisting of Chapters 2 to 4 we investigate the path structure of local tournaments and in-tournaments. The first problem we deal with in Chapter 2 is to develop the structure necessary for a local tournament to be not arc-traceable, i.e. to contain an arc that does not belong to a Hamiltonian path. Using this structure we give various sufficient criteria for a local tournament to be arc-traceable. Our results extend those of Busch, and Busch, Jacobson and Reid for tournaments. In the next two chapters - Chapters 3 and 4 - we focus on shorter paths in local tournaments and in-tournaments. We study and confirm a conjecture of Volkmann and, subsequently, consider variations of Volkmann's problem. The second part of this thesis consists of two chapters in which we investigate the following problem: How many non-separating vertices has a strongly connected local tournament or in-tournament in terms of minimum vertex degree? In Chapter 5 we generalize results of Kotani for tournaments and of Meierling and Volkmann for local tournaments. The topic of Chapter 6 is the problem of vertex deletion, where we ask for the existence of two distinct vertices in a strongly connected local tournament whose removal preserves the strong connectivity of the digraph. We characterize all local tournaments with exactly two such vertices thereby generalizing a result of Las Vergnas for tournaments. The third part of this thesis is devoted to the cycle structure of local tournaments and in-tournaments. A reformulation of the results of Chapter 6 shows that we characterized all local tournaments with exactly two cycles of length order minus one. Using a special parameter, the quasi-girth of a local tournament, we investigate in Chapter 7 how many cycles of a given length, a strongly connected local tournament has at the least. This problem has already been studied and solved completely by Moon, and Las Vergnas for tournaments and our results generalize those of Las Vergnas. The interesting problem of complementary cycles in strongly connected local tournaments is investigated in Chapter 8. In 1996 Guo and Volkmann solved the question whether a 2-connected local tournament has complementary cycles in characterizing the exceptional digraphs. This result was generalized and extended in various forms. For example, Meierling and Volkmann characterized all 2-connected in-tournaments that are not cycle complementary. In this chapter we investigate the structure of strongly connected, but not 2-connected, local tournaments that are not cycle complementary. As applications we present sufficient criteria for a strongly connected local tournament to have k vertex disjoint cycles that span its vertex set. Our results extend and generalize those of Li and Shu for tournaments. In the last chapter we consider extendable cycles in strongly connected in-tournaments. In 1989 this property was introduced by Hendry in the context of general digraphs and subsequently studied by Tewes and Volkmann for in-tournaments. We solve a conjecture of Tewes and Volkmann in the affirmative.

Fulltext:
PDF