The H-force Set And The H-force Number Of Several Families Of Cartesian Product Graphs

In the graph theory, the problems related to the circles are one of the key points. In recent years, a large number of researchers have paid attention to the problems of hamiltonian cycles. As the scholars I.Fabrici, E.Hexel, S.Jendrol proposed the concepts of H-force set and H-force number of hamiltonian graphs, the H-force set and the H-force number of hamiltonian graphs have also become the focus of research scholars.In this thesis, we study the H-force set and the H-force number of several Cartesian product graphs. The investigation to the H-force set and H-force number of these graphs, on one hand, will deepen our understanding of the structure of Hamilton graph, on the other hand, will help improving the algorithm for looking for hamiltonian cycles in these graphs. In addition, this thesis also discusses the questions of hamiltonian properties of the strongly round local tournament.The thesis consists of four sections.Chapter 1 is the preface. The background and basic concept are introduced.In Chapter 2, we consider the H-force set and H-force number of the Cartesian product of a cycle with a path in graphs.The graph of the Cartesian product of a cycle with a path is obtained by the definition of Cartesian product. An exploration is made on the H-force set and H-force number of these graphs. By using the method of searching non-hamiltonian cycles, we prove the conclusion:Let G=Ckx Pl, in which k≥2,l≥1. Then(i) When k=2, h(G)=2.(ii) When k≥3,In Chapter 3, we consider the H-force set and H-force number of the Cartesian product of a cycle with a path in digraphs. And get the following theorem:Let Cn and Ckn be cycles in digraph, where n is positive integer and n≥2, k=1,2, Then(i) Cn×Ckn is hamiltonian.In Chapter 4, we study the questions of hamiltonian decomposition of the strongly round local tournament and get a few several conclusions related to the hamiltonian properties.1. A 3-arc-strong round local tournament D contains two arc-disjoint hamiltonian cycles.2. Let D be a locally semicomplete digraph which is obtained from C22k by adding a new vertex x, at least two arcs from x to V(C22k) and at least two arcs from V(C22k) to x. Then D contains two arc-disjoint hamiltonian cycles.3. Let D is a 2-arc-strong round local tournament, then D contains arc-disjoint hamil-tonian cycle and hamiltonian path if and only if D is not the second power of an even cycle.