Hamiltonian cycles in certain graphs and out-arc pancyclic vertices in tournaments

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.

Grantor dc:publisher

Mainz

Year dc:date

2008

Author dc:creator

• Feng, Jinfeng

Contributors dc:contributor

• Guo, Yubao

• info:eu-repo/classification/ddc/510
• Turnier <Mathematik>
• Hamilton-Kreis
• Graphentheorie
• Mathematik
• graph theory
• digraph
• tournament
• hamiltonian cycle

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-112534%22

OAI record oai:identifier

https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A49967