2008
Zugl.: Aachen, Techn. Hochsch., Diss., 2008
Zsfassung in engl. und dt. Sprache
Genehmigende Fakultät
Fak01
Hauptberichter/Gutachter
Tag der mündlichen Prüfung/Habilitation
2008-01-24
Online
URN: urn:nbn:de:hbz:82-opus-22110
URL: https://publications.rwth-aachen.de/record/49967/files/Feng_Jinfeng.pdf
Einrichtungen
Inhaltliche Beschreibung (Schlagwörter)
Turnier <Mathematik> (Genormte SW) ; Hamilton-Kreis (Genormte SW) ; Graphentheorie (Genormte SW) ; Mathematik (frei) ; graph theory (frei) ; digraph (frei) ; tournament (frei) ; hamiltonian cycle (frei)
Thematische Einordnung (Klassifikation)
DDC: 510
msc: 05C38 Path * 05C45 Eule * 05C20 Dire
Kurzfassung
In der vorliegenden Arbeit beschäftigen wir uns zunächst mit hamiltonschen Graphen. Im Allgemeinen gibt es zwei wichtige Gruppen von den hinreichenden Bedingungen für die Existenz eines Hamiltonkreises in einem Graphen: die sogenannten Grad-Bedingungen sowie die „verbotene Teilgraph“ -Bedingungen. Durch das Kombinieren beider werden einige neue hinreichende Bedingungen für die Existenz eines Hamiltonkreises in einem Graphen vorgestellt: z. B. in 2-schweren und fast abstandstreuen Graphen; in den klauenfreien Graphen mit einer Ore-Typ-Bedingung; in den klauenfreien und sanduhrfreien Graphen mit einer Fan-Typ-Bedingung. Danach wird eine von den Herren Bang-Jensen und Gutin vorgestellte Vermutung über die Existenz eines echt gefärbten Hamiltonweges in einem gefärbten vollständigen Graphen bewiesen und eine Charakterisierung für die Existenz von komplementären Kreisen in Jump-Graphen gegeben. Im zweiten Teil dieser Arbeit werden Turniere betrachtet. Yao, Guo und Zhang vermuteten, dass jedes k-fach stark zusammenhängende Turnier k Ecken enthält, so dass jeder Außenbogen von solchen Ecken panzyklisch ist. Die Richtigkeit für k=1 wurde von ihnen bewiesen. Für k=2, 3 wird die Vermutung in dieser Arbeit gezeigt. Yeo fand eine unendliche Klasse von k-fach stark zusammenhängenden Turnieren, wovon jedes höchstens 3 solche Ecken enthält. Abschliessend wird in dieser Arbeit gezeigt, dass jedes k-fach (k>=2) stark zusammenhängende Turnier mindestens k+1 Ecken enthält, so dass alle Außenbögen der Ecken 4-panzyklisch sind.In the first part of this thesis, some new sufficient conditions for a graph to be Hamiltonian and some other results on related topics are introduced. Generally speaking, there are two important types of sufficient conditions: the so-called degree conditions and the typical forbidden subgraph conditions. By combining those two types, some new sufficient conditions are found: 2-heavy and almost distance-hereditary graphs; claw-free graphs with an Ore-type condition; claw-free and hourglass-free graphs with a Fan-type condition. Moreover, this part deals with a conjecture introduced by Bang-Jensen and Gutin about the existence of a properly colored Hamiltonian path in an edge-colored complete graph, and deals with the existence of the complementary cycles in jump graphs. In the second part of this thesis, tournaments are considered . Yao, Guo and Zhang conjectured that each k-strong tournament contains k vertices whose out-arcs are pancyclic. They proved that this is true for k=1. In this thesis, the conjecture is also verified for k=2, 3. Yeo found an infinite class of k-strong tournaments, each of which contains at most 3 such vertices. This gives rise to an interesting problem: How many vertices does a tournament contain such that all out-arcs of those vertices are 4-pancyclic? At last, it is shown that each k-strong tournament with k>=2 contains at least k+1 vertices whose out-arcs are 4-pancyclic.
Fulltext:
PDF
Dokumenttyp
Dissertation / PhD Thesis
Format
online, print
Sprache
English
Externe Identnummern
HBZ: HT015464248
Interne Identnummern
RWTH-CONV-112534
Datensatz-ID: 49967
Beteiligte Länder
Germany