Close to regular multipartite tournaments [Elektronische Ressource] / vorgelegt von Stefan Winzen

Sujets

• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2004
• Nombre de lectures: 25
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Close to Regular Multipartite Tournaments
Von der Fakult˜ at fur˜ Mathematik, Informatik und Naturwissenschaften
der Rheinisch-Westf˜ alischen Technischen Hochschule Aachen
zur Erlangung des akademischen Grades
eines Doktors der Naturwissenschaften
genehmigte Dissertation
vorgelegt von
Diplom-Mathematiker
Stefan Winzen
aus Rheydt (heute M˜ onchengladbach)
Berichter: Professor Dr. Lutz Volkmann
Universit˜ atsprofessor Dr. Eberhard Triesch
Tag der mundlic˜ hen Prufung:˜ 10.12.2004
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online
verfugbar.˜Danksagung
An erster Stelle m˜ ochte ich meinem Betreuer Herrn Prof. Dr. Lutz Volkmann
danken. Durch seine Vorlesungen habe ich einen interessanten Einblick in die
Graphentheorie bekommen, ein Gebiet, das ich immer mehr zu sch˜ atzen gelernt
habe. Die t˜aglichen ,,Kafieepausen" und weitere Gespr˜ ache mit Herrn Prof.
Volkmann lieferten mir zahlreiche Anregungen und Hinweise, die schlie…lich zu
der Dissertation fuhrten,˜ so wie sie jetzt vorliegt.
Des weiteren gilt mein Dank Herrn Prof. Dr. Eberhard Triesch, dem Inhaber
des Lehrstuhls II fur˜ Mathematik. Unter seiner umsichtigen Fuhrung˜ war ich
zun˜ achst als wissenschaftliche Hilfskraft und schlie…lich als wissenschaftlicher
Angestellter an seinem Lehrstuhl t˜atig. Zudem stellte er sich als Korreferent
fur˜ diese Dissertation zur Verfugung.˜
Der Konrad-Adenauer-Stiftung e.V. danke ich fur˜ ihre Unterstutzung˜ durch
ein Stipendium. Neben einer flnanziellen F˜ orderung wurde mir in Seminaren
die M˜ oglichkeit geboten, auch einmal ub˜ er den Tellerrand zu schauen und an
zus˜ atzliches Wissen au…erhalb der Mathematik zu gelangen. Au…erdem wurde
mir mit der Aachener Stipendiatengruppe ein neuer Freundeskreis aufgetan.
Ein weiterer Aspekt, der wichtig fur˜ das Zustandekommen dieser Dissertation
war, ist das freundschaftliche Arbeitsklima, fur˜ das ich mich bei den Mitar-
beitern am Lehrstuhl II fur˜ Mathematik herzlich bedanken m˜ ochte. Insbeson-
dere seien hier meine ,,Zimmergenossen" Frank Jelen, Torsten Kornefiel, Dirk
Kremer und Irene Stella, sowie unsere Sekret˜ arin Frau Hannelore Volkmann
erw˜ ahnt, die immer geduldig waren, meine Fragen zu beantworten. Frau Irene
Stella danke ich fur˜ eine gute Zusammenarbeit, die zu einem interessanten
Teilergebnis der Dissertation fuhrte.˜
Es ist mir auch wichtig, meinen Freunden aus Aachen, M˜ onchengladbach und
inzwischen einigen anderen Gebieten Deutschlands zu danken. Zahlreiche
Abende gefullt˜ mit DSA-, Badminton- oder Fu…ballspielen, Filme im Kino
oder auf Video schauen, mit Doppelkopf- oder Gesellschaftsspielrunden und
anderen Aktivit˜ aten sorgten fur˜ einen gesunden Ausgleich zu der Arbeit.
Colin Hirsch und Herrn Prof. Dr. Lutz Volkmann danke ich fur˜ das Korrek-
turlesen der Einleitung.
Mein letzter und gr˜ o…ter Dank richtet sich an meine Eltern, die mich immer
in verschiedenster Art und Weise unterstutzt˜ haben. Vielen Dank fur˜ alles.
Aachen, im Juli 2004 Stefan WinzenPreface
In the last forty years Graph Theory has undergone an extensive and rapid
development. One branch of Graph Theory, which is important for solving dis-
crete organization and optimization problems, is the theory of directed graphs,
or digraphs. The best studied class of directed graphs are the tournaments.
Already in 1934 R¶edei [21] proved that every tournament contains a Hamil-
tonian path. Other classical results can be found in the works of Camion [7],
Moon [20], Harary and Moser [17] or Alspach [1].
Tournaments can be generalized to the class of semicomplete multipartite
digraphs or to multipartite tournaments. A c-partite tournament is an ori-
entation of a complete mutlipartite graph and a multipartite
digraph is obtained by replacing each edge of a complete multipartite graph
by an arc or by a pair of mutually opposite arcs. These domains have only
recently received attention in fundamental research. A very profound work,
whose results will often be used throughout this thesis, is the Ph. D. thesis of
Yeo [49]. Further results and surveys on the subject are the Habilitation thesis
of Guo [9], the Ph. D. thesis of Tewes [23] and the articles [15] of Gutin and
[31] of Volkmann.
In this thesis we will mainly examine the existence of directed cycles and
directed paths (or short cycles and paths, respectively) with certain properties
in multipartite tournaments. The example of an extended transitive tourna-
ment demonstrates that there are multipartite tournaments without any cycle
and only with short paths. Since extended transitive tournaments are not
strongly connected one approach is to analyze only strongly connected mul-
tipartite tournaments as done in [11] by Guo, Pinkernell and Volkmann. In
this thesis the statements on the existence of cycles and paths depend on how
much a multipartite tournament difiers from being regular. Hence, we use a
parameter introduced by Yeo [51], the global irregularity i (D) of a digraph D,g
which is deflned to be the difierence between the maximum and the minimum
occuring vertex-degree in D (out- or indegree). If i (D) = 0, then D is regular,g
and if i (D)• 1, then D is called almost regular.g
This thesis is divided into three parts and eight chapters. In the flrst
part, we study the existence of certain cycles in close-to-regular multipartite
tournaments. The short second part, only consisting of Chapter 5, presents
an analysis and an improvement of a result of Yeo [49] on the connectivity
of close-to-regular multipartite tournaments. These results are useful for the
third part of this thesis, in which we will mainly search for long paths in
multipartite tournaments.
iiiiv
Chapter 1 contains an introduction to the terminology and notation used
throughout this text. Furthermore, we present some results on the possible
degrees of vertices in multipartite tournaments of a given global irregularity
i (D).g
In Chapter 2, at the beginning of Part I, we take a look at the existence
of cycles in almost regular multipartite tournaments whose length does not
exceed the number of partite sets and which contain a given arc. Extending
results of Alspach [1], Guo [9] and Volkmann [30, 32], we flnd an optimal
integer c of partite sets of an almost regular c-partite tournament to ensure
the existence of cycles of all lengths p with p 2 f4; 5;::: ;cg through a given
arc. In detail, we distinguish the cases that there are at least two vertices in
each partite set and that there is only one vertex in at least one partite set.
Chapter 3 also deals with cycles containing a given arc. But in contrast to
Chapter 2, here the length of the cycles does not matter. Instead the number
of partite sets the cycles include is considered. Inspired by a result of Goddard
and Oellermann [8], Guo and Kwak [10] proved that every arc of a regular
c-partite tournament D with c‚ 4 is contained in a cycle with vertices from
exactly m partite sets for all 4• m• c. We extend this theorem to almost
regular multipartite tournaments, and we show that the bounds we give are
optimal in some sense.
In Chapter 4 we try to combine the themes of the last two chapters by
searching for cycles of a given length and a given number of partite sets. The
problem is to flnd su–cient conditions for a multipartite tournament to con-
tain a cycle consisting of a given number of vertices from each partite set. At
flrst, solving a problem of Volkmann [29], we show that every almost regular
multipartite tournament with at least 5 partite sets contains a strongly con-
nected subtournament of maximal order and thus, according to a well-known
result of Moon [20], a cycle consisting of exactly one vertex from each partite
set. Furthermore, we flnd cycles with zero or one vertex from each
partite set of a multipartite tournament with a given flxed global irregularity
i (D) ‚ 2. The number of partite sets that contribute exactly one vertexg
to the cycle depends on the global irregularity and on the number of partite
sets. In the last section of the fourth chapter, we look for long cycles. Since,
according to a result of Yeo [48], every regular multipartite tournament D
is Hamiltonian, the next question is that of which mts
contain a cycle with all but one vertex from each partite set. We prove that
a regular c-partite tournament D with c‚ 3 and at least two vertices in each
partite set contains a cycle with all but one vertex from each partite set with
the exception of when c = 4 and there are two vertices in every partite set of
D.
The second part of this thesis only consists of Chapter 5, which deals with
connectivity in multipartite tournaments. In particular we study a bound for
the (vertex-) connectivity developed by Yeo [51]. Since this bound is very
useful for many applications, an interesting problem is to characterize the
multipartite tournaments that realize this bound. Analyzing the proof of Yeo,
we flrst flnd necessery conditions for a multipartite tournament to realize Yeo’s
bound. We obtain the structure of these multipartite tournaments. Second,v
using the conditions and certain classes of examples, we characterize all almost
regular multipartite tournaments, which realize the bound.
In Chapter 6, at the beginning of Part III, we return to the problem of
Chapter 4, but in a weaker form applied to paths. We look fo