Hamiltonicity Of Almost Regular Multipartite Tournaments And Several Count Problems Of Digraphs

The main content of this thesis deals with three aspects of digraphs: Hamil-tonicity of almost regular multipartite tournaments, the low bound of the number of Hamilton-path in tournaments and the count problems of all the dominating sets for several special classes of digraphs.A multipartite or n-partite tournament is an orientation of a complete n-partitegraph. A tournament is an n-partite tournament that contains just n vertices.letx be a vertex of the digraph D. We denote the outdegree and indegree of x byd_D~+(x) and d_D~-(x), respectively. The irregularity of a digraph D = (V, A) is defined byI(D) = max {| d~+(x) - d~-(y) |}. If I(D)≤1, then D is called almost regular , and if I(D) = 0, D is regular.Hamiltonicity of digraphs , as the intrinsic challenge itself and wide applications, is one of popular problems in digraph theory. Until now, there have been rather abundant results. In 1966, Moon[16] proved that the strong tournament is vertex pancyclic firstly. In 1976, Bondy[3] proved the strong n-partite tournament contains an m-cycle, for every m ∈ {3,4,...,n}. Yeo[18] showed that regular multipartite tournament is Hamiltonian. Zhou Guofei and Zhang Kemin[21] showed that almost regular n-partite (n ≥ 7) tournament is Hamiltonian in 1999. This paper generalizes the result above and obtains the following theorem:Almost regular n-partite (n ≥ 6) tournament is Hamiltonian.To the research of digraphs, many references consider mainly the existence of Hamilton-paht for digraphs, but the references are less about the number of Hamilton-path. In section 2.2 of this paper ,through considering the strong components of tournament, we obtain the theorem:Let T be a tournament and T1, T2, ? ? ?, Ts be the strong components of T (s = 1, when T is strong).If m denotes the number of Hamilton-path in T, The equation is true if and only if for every i e {1,2,... s}. This theorem gives a low bound of the number of Hamilton-path in tournaments, and this bound is sharp.A subset D C V(H) is a dominating set of digraph H, if for any vertex y ∈ V(H) - D, there exists x∈ D such that xy ∈ A{H). Let d{H) denote the number of...