Publikationsserver der RWTH Aachen University
K-ordered graphs and out-arc pancyclicity on digraphs
Abstract
dc:descriptionOver the years Hamiltonian graphs have been widely studied. Various Hamiltonian-related properties have also been considered. Some of the properties are weaker, for example traceability and existence of a cycle factor in graphs, while other are stronger, for example Hamiltonian-connectivity, pancyclicity and panconnectivity. In 1997, L. Ng and M. Schultz introduced the idea of cycle orderablity and gave a new strong Hamiltonian property. A graph is called k-ordered Hamiltonian if for every ordered sequence of k vertices, there is a Hamiltonian cycle that encounters the vertices of the sequence in the given order. As shown recently, there are many conditions that imply Hamiltonicity can also imply the stronger property of k-ordered Hamiltonian if we give a slight modification. Our first work is the new sufficient conditions in terms of degree sum on distance 2 vertices for a graph to have a k-ordered Hamiltonian cycle. These conditions are given not only on the lower connectivity but also on the upper connectivity. Additionally, the traceability and Hamiltonicity have also been proved under degree sum conditions on distance 2 vertices. We have showed the sharpness of these conditions as well as the independence of these results. Our second work is the introduction of a new pancyclicity of graphs, "(k,m)-vertex-pancyclic ordered" graphs which is a generalization of both k-ordered and vertex-pancyclic graphs. This idea comes from the "(k,m)-pancyclic ordered" introduced by R. J. Faudree, R. J. Gould, M. S. Jacobson and L. Lesniak, which is the generalization of both k-ordered and pancyclic graphs. Note that every (k,m)-vertex-pancyclic ordered graph is (k,m)-pancyclic ordered. We have proved that a graph is (k,m)-vertex-pancyclic ordered under the same minimum sum of degree conditions of non-adjacent vertices as required by the (k,m)-pancyclic ordered graphs. As an important branch of graph theory, the area of digraphs has developed enormously within the last four decades. There are large numbers of topics on digraphs. Out-arc pancyclicity is one of the newest and most interesting themes on digraphs, which deals with the existence of the vertices whose all arcs out of them are pancyclic. Our third work is the investigation of the vertices, with the property that all arcs out of them are pancyclic and 4-pancyclic in a k-strong tournament. We have only considered 2- and 3-strong tournaments since A. Yeo presented an infinite class of k-strong tournament, such that each tournament contains at most 3 such vertices. We have showed that every k-strong tournament contains at least k vertices whose all arcs out of them are pancyclic for k=2,3. If 3-cycles are not considered, we have proved that every s-strong tournament with s > 2 contains at least s+1 vertices whose all arcs out of them are 4-pancyclic. Our fourth work is the structural analysis of special locally in-semicomplete digraphs, namely, positive-round digraphs. We have given a sufficient condition for a strong digraph to be positive-round and a characterization of strong positive-round oriented digraphs. Our last work is the new sufficient conditions for a digraph to be strongly Hamiltonian-connected. Path-contraction is a powerful tool in the proof of out-arc pancyclicity on tournaments. We have brought forward its additional applications on strongly Hamiltonian-connected digraphs and given the sufficient conditions involving minimum semi-degree, minimum degree sum and the number of arcs to force a digraph to be strongly Hamiltonian-connected.
Degree
thesis:*- Grantor dc:publisher
- Publikationsserver der RWTH Aachen University
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Li, Ruijuan
- Contributors dc:contributor
-
- Guo, Yubao
Subjects
dc:subject × 8Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- eng