Local tournaments and in tournaments [Elektronische Ressource] / vorgelegt von Dirk Meierling
175 pages
Deutsch

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Local tournaments and in tournaments [Elektronische Ressource] / vorgelegt von Dirk Meierling

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
175 pages
Deutsch
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Local Tournaments and In-TournamentsVon der Fakult¨at fu¨r Mathematik, Informatik und Naturwissenschaftender Rheinisch-Westf¨alischen Technischen Hochschule Aachenzur Erlangung des akademischen Gradeseines Doktors der Naturwissenschaftengenehmigte Dissertationvorgelegt vonDiplom-MathematikerDirk Meierlingaus HagenBerichter: Professor Dr. Lutz VolkmannUniversit¨atsprofessor Dr. Eberhard TrieschTag der mu¨ndlichen Pru¨fung: 28.11.2007DieseDissertationistaufdenInternetseitenderHochschulbibliothekonlineverfu¨gbar.DanksagungBedanken m¨ochte ich mich an dieser Stelle bei allen, die mich bei der Erstellungdieser Arbeit unterstu¨tzt haben. Mein besonderer Dank gilt meinem BetreuerHerrn Professor Dr. Lutz Volkmann, in dessen Vorlesungen und Seminaren meinInteresse fu¨rdie Graphentheorie geweckt wurde. Zahlreiche Gespr¨ache undfrucht-bare Diskussionen schufen ein besonderes Arbeitsklima und waren Grundlage fu¨rviele wertvolle Hinweise und Anregungen.Des Weiteren danke ich dem Inhaber des Lehrstuhls II fu¨r Mathematik, HerrnProfessor Dr. Eberhard Triesch, der sich als Korreferent dieser Dissertation zurVerfu¨gung stellte.Weiterer Dank gilt allen Mitarbeitern des Lehrstuhls II fu¨r Mathematik, die zurfreundschaftlichen Arbeitsatmosph¨arebeitrugen. Indiesem Zusammenhangdankeich auch unserer Sekret¨arin Frau Hannelore Volkmann, die einen großen Anteildaran hatte.

Sujets

Informations

Publié par
Publié le 01 janvier 2007
Nombre de lectures 17
Langue Deutsch

Extrait

Local Tournaments and In-Tournaments
Von der Fakult¨at fu¨r 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
Dirk Meierling
aus Hagen
Berichter: Professor Dr. Lutz Volkmann
Universit¨atsprofessor Dr. Eberhard Triesch
Tag der mu¨ndlichen Pru¨fung: 28.11.2007
DieseDissertationistaufdenInternetseitenderHochschulbibliothekonlineverfu¨gbar.Danksagung
Bedanken m¨ochte ich mich an dieser Stelle bei allen, die mich bei der Erstellung
dieser Arbeit unterstu¨tzt haben. Mein besonderer Dank gilt meinem Betreuer
Herrn Professor Dr. Lutz Volkmann, in dessen Vorlesungen und Seminaren mein
Interesse fu¨rdie Graphentheorie geweckt wurde. Zahlreiche Gespr¨ache
undfruchtbare Diskussionen schufen ein besonderes Arbeitsklima und waren Grundlage fu¨r
viele wertvolle Hinweise und Anregungen.
Des Weiteren danke ich dem Inhaber des Lehrstuhls II fu¨r Mathematik, Herrn
Professor Dr. Eberhard Triesch, der sich als Korreferent dieser Dissertation zur
Verfu¨gung stellte.
Weiterer Dank gilt allen Mitarbeitern des Lehrstuhls II fu¨r Mathematik, die zur
freundschaftlichen Arbeitsatmosph¨arebeitrugen. Indiesem Zusammenhangdanke
ich auch unserer Sekret¨arin Frau Hannelore Volkmann, die einen großen Anteil
daran hatte.
Fu¨r das Korrekturlesen und ihre Geduld mit meinen Problemen aus der Welt der
Graphentheorie m¨ochte ich besonders Frau Anja Schutzbach danken.
Schließlich danke ich meinen Eltern fu¨r ihre Unterstu¨tzung.
Aachen, im Dezember 2007 Dirk MeierlingPreface
Tournaments constitute perhaps the most well-studied class of directed graphs.
One of the reasons for the interest in the theory of tournaments is the monograph
Topics on Tournaments [58] by Moon published in 1968, covering all results on
tournaments known up to this time. In particular, three results deserve special
mention: in 1934R´edei [60]proved thatevery tournament hasa directed
Hamiltonian path, in 1959 Camion [27] showed that every strongly connected tournament
has a directed Hamiltonian cycle and in 1966 Moon [57] published his famous
theorem which says that every strongly connected tournament on n vertices is vertex
pancyclic, i.e. every vertex is contained in a directed cycle of length 3,4,...,n.
The latter result is a strong improvement of Camion’s theorem and can be
considered a milestone in the investigation of the cycle structure of tournaments. In
the following years survey articles dealing with tournaments were contributed by
Beineke and Wilson [20] in 1975, Reid and Beineke [63] in 1978, Beineke [19] and
Bermond and Thomassen [21] in 1981, Bang-Jensen and Gutin [10] and Reid [62]
in 1996. All these articles kept the interest of mathematicians working in this field
growing.
There are various generalizations of tournaments: local tournaments and
locally
semicompletedigraphs,in-tournamentsandlocallyin-semicompletedigraphs,multipartitetournaments andsemicomplete multipartitedigraphs, quasi-transitive
digraphs and several others. For a comprehensive overview of multipartite
tournaments and semicomplete multipartite digraphs the reader may be referred to the
survey articles of Gutin [40] and Volkmann [75, 78], and for a summary of the
remaining classes to the article of Bang-Jensen and Gutin [11]. It is a natural
question to ask which of the results for tournaments can be extended to one of its
generalized classes. In view of R´edei’s and Moon’s theorems, the path and cycle
structure are specifically of interest. In this thesis, two different generalizations of
tournaments are considered, namely the class of local tournaments and the class
of in-tournaments. For the sake of simplicity, directed paths and directed cycles
are called paths and cycles throughout this thesis.
vvi Preface
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. This class, or more generally the class of locally
semicomplete digraphs whose members might have cycles of length two, was
introduced by Bang-Jensen [3] in 1990. Three years later, Bang-Jensen, Huang and
Prisner [16] introduced a further generalization of local tournaments, the class
of in-tournaments, in claiming adjacency only for vertices that have a common
out-neighbor. 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. Other such classes are, for
example, quasi-transitive digraphs (cf.[14]) andarc-locally semicomplete digraphs
(cf. [7]).
Ever since Bang-Jensen introduced theclass oflocaltournaments, a lotof research
has been done in this field. In particular the Ph.D. theses of Huang [45] and
Guo [33] handled this subject in detail.
Concerning in-tournaments and, in particular, the path and cycle structure of
in-tournaments, some initial fundamental results were presented by Bang-Jensen,
Huang and Prisner [16]. Further work on pancyclicity and the cycle structure of
in-tournaments has been done by Tewes and Volkmann [68, 69], Tewes [66, 67]
and Peters and Volkmann [59]. The reader may be referred to the Ph.D. thesis of
Tewes [65] for an overview of this subject.
In this thesis we study the path and cycle structure of local tournaments and
intournaments 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.
InthefirstpartconsistingofChapters2to4weinvestigatethepathstructureoflocal tournaments and in-tournaments. The first problem we deal with in Chapter 2
istodevelopthestructurenecessaryforalocaltournamenttobenotarc-traceable,
i.e. tocontainanarcthatdoesnotbelongtoaHamiltonianpath.
Usingthisstructure we give various sufficient criteria for a local tournament to be arc-traceable
and we present examples that show the sharpness of our conditions. Our results
extend those of Busch [25] and Busch, Jacobson and Reid [26] for tournaments.
In the next two chapters — Chapters 3 and 4 — we focus on shorter paths in
local tournaments and in-tournaments. We show that a strongly connected
intournament on at least 2m−2 vertices, where m≥ 4, with the property that each
arc lies on a path of order at least m, contains at most one m-path arc, i.e. an arc
such that the longest path through it is of order m. This confirms a conjecture
of Volkmann [74]. Subsequently we study two variations of the above problem.Preface vii
Firstly we lower the requirement on the order of the in-tournament in question to
n ≥ 2m−3 (Chapter 3) and secondly we consider local tournaments instead of
3m−2in-tournaments, allowing the local tournament to be of order as low as n≥
2
though (Chapter 4). Finally we present examples that show the sharpness of our
results in terms of order n.
The second part of this thesis consists of two chapters in which we investigate the
following problem: How many non-separating vertices does a strongly connected
local tournament or in-tournament have in terms of minimum vertex degree? In
Chapter 5 we prove that every strongly connected in-tournament D on n vertices
withminimumdegreeδ(D)≥ p≥ 2hasatleastk = min{n,4p−2}non-separating
vertices. If n ≥ 4p or if n ≥ 4p+1 and p ≥ 3, this proposition can be improved
to k = 4p−1 and k = 4p, respectively, unless D is a member of a well-described
exceptional family. The results in this chapter generalize those of Kotani [50] for
tournaments andof Meierling andVolkmann[55]forlocaltournaments. Thetopic
ofChapter6istheproblemofvertexdeletion,whereweaskfortheexistenceoftwo
distinct vertices ina stronglyconnected localtournament 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 [51] 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 on n vertices with exactly two cycles
of length n−1. Using the parameter g(D), called quasi-girth of a local
tournament D, Bang-Jensen, Guo, Gutin and Volkmann [8] proved that every strongly
connected local tournament is vertex (g(D)+1)-pancyclic. In Chapter 7 we
investigate how many cycles of length r, where g(D)+1 ≤ r ≤ n−1, a strongly
connected local tournament has at the least. This problem has already been
studied and solved completely by Moon [57] and Las Vergnas [51] for tournaments and
ourresultsgeneralizethoseofLasVergnas.
Theinterestingproblemofcomplementary cycles in strongly connected local tournaments is investigated in Chapter 8.
In 1996 Gu

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents