Hamilton Paths And Panpathical Vertices-Pairs In Digraphs

This paper are composed of two chapters, in which we study the hamiltonian paths in locally in(out)-semicomplete digraphs and extended locally in(out)-semicom-plete digraphs, and we also study panpathical vertices-pair in tournaments and extended tournaments.In the first chapter, Hamilton path problems are discussed. Some definitions and relative results are given in section 1.1. In section 1.2, two sufficient conditions for the existence of a hamiltonian path in a locally in-semicomplete digraph are described, which are listed as follow: (i) Let D be a connected locally in-semicomplete digraph of order n≥ 2. Suppose that for every dominated pair of non-adjacent vertices {x, y}, either d(x) ≥ n and d(y) ≥ n — 1, or d{x) ≥ n — 1 and d(y)≥ n, then D is traceable, (ii) Let D be a connected locally in-semicomplete digraph of order n> 2. Suppose that D satisfies min{d~+(x) + d~-(y), d~-(x)+d~+(y)} ≥ n — 1 for every dominated pair of non-adjacent vertices {x, y}, then D is traceable. Used the property of the reverse digraphs, two similar results are obtained for locally out-semicomplete digraphs. In section 1.3, we show a sufficient condition for an extended locally in-semicomplete digraph to be traceable. The result is that let D be a connected extended locally in-semicomplete digraph of order n≥ 2. If either d{x) ≥ n and d{y) ≥ n — 1 or d(x) ≥ n — 1 and d(y) ≥ n, and d(u) ≥ n — 1, d(v) ≥ n — 1 for every dominated pair of non-adjacent vertices {x, y} and every dominating pair of non-adjacent vertices {u, v}, then D is traceable. Moreover, there is a similar result in extended locally out-semicomplete digraphs.In the second chapter, panpathical vertices-pairs in tournaments and panpathical vertices-pairs in extended tournaments are discussed. In section 2.2, we prove that every cnonected but not strongly cnonected tournament contains a pair of vertices {u, v} such that {u, v} are panpathical vertices-pairs, and give a polynomial algorithm to find those two vertices. Another result that every transitive tournament contains only a pair of panpathical vertices is presented in this section. Two sufficient conditions for an extended tournament to have panpathical vertices-pairs are formulated in section 2.3. Furthermore, we prove that if D be a transitive extended tournament but not tournament, then D does not contain panpathical vertices-pairs.