The Research For The (1,2)-step Competition Graphs And The H-force Sets Of The Local Semicomplete Digraphs

Tournaments form perhaps the most important and interesting class of directed graphs and have a very rich theory which has no analog in the theory of undirected graph. In 1990, a very important class of directed graphs were introduced by Bang-Jensen, i.e. locally semicomplete digraphs which include many useful properties and conclusions analog to tournaments. Therefore, the research into the struc-ture and the applications of such digraphs has been paid close attention by many researchers. Since the definition of it has been given, the research of the locally semicomplete digraph has evolved into a very productive area.The competition graph of a digraph derived from a biological problem. It was introduced by Cohen in 1968 associated with the study of ecosystems. Fur-thermore, the various application of the competition graph and its generalizations include applications to channel assignments, coding, and modeling of complex eco-nomic etc. Therefore, it has been a research topic with great application background in graph theory. In 2011, Factor et al. introduced the definition of the (1,2)-step competition graph, which is an important generalization of competition graph. Since the definition of the (1,2)-step competition graph was introduced, it adds new contents on the research of the competition graph and its generalizations, and expands the scope of the study.As everyone knows, hamiltonian circle which have a rich theory is always the topics, which has attracted widespread by a lot of researchers on graph theory. However, most of the research results have been about the sufficient conditions. The definition of the H-force set and the H-force number were introduced firstly by Fabrici et al. in 2009. According to the definition, we suppose that there exists one hamiltonian cycle at least in the graph, which provides a new way of thinking to study the hamiltonian circle problems from the perspective of necessity.The thesis consists of four chapters. In Chapter 1, after a brief introduction to the contents and significance of this work, the used basic notation and terminology on digraphs and the properties, we list our main results. The structure of a locally semicomplete digraph and some important results are introduced in Chapter 2. The problem of the (1,2)-step competition graph of a locally semicomplete digraph is studied in Chapter 3. The problem of the H-force set and the H-force number of a locally semicomplete digraph is studied in the last chapter.A pure local tournament is a local tournament which is not a tournament. In Section 3.2 of Chapter 3, the structure of the (1,2)-step competition graph of a pure local tournament is studied and characterized. The structure of the (1,2)-step competition graph of a local tournament is characterized completely by this results together with the structure by Factor et al. Moreover, the (i,k)-step com-petition graph of a round decomposable locally semicomplete digraph is studied in Section 3.3 of Chapter 3, which is another subclass of locally semicomplete digraph-s. Through the discussion of the distance between any two vertices of a digraph D, a sufficient and necessary condition for any two vertices of D to be adjacent in the (i,k)-step competition graph Ci,k(D) is given. Consequently, the structure of Ci,k(D) is characterized.In Section 4.1 of Chapter 4, we study the H-force set and the H-force number of a locally semicomplete digraph. In this section, we extend the definition of the H-force set and the H-force number in undirected graph to the directed graph. At the same time, the minimal H-force sets of locally semicomplete digraphs are characterized and the H-force number is given. On this basis, the definitions of the H-force set and the H-force number are extended on hypertournaments by using cycles of hypertournaments instead of the cycles of undirected graphs and, the smallest possible H-force set of a k-hypertournament with n≥k+3 vertices is characterized and its H-force number is given unless it belongs to the exceptional classes of k-hypertournaments in Section 4.2 of Chapter 4.