Research On The (1,2)-step Competition Graphs Of Extended Tournaments And Round Digraphs

In the eco-systerm, the competition graph was originally taken as the mathematical model to represent the predatory relation between species. As the predatory relation becomes more complicated, the competition graph has boundeness. In view of this, somebody make great efforts to generalize the concept of competition graph, among which the (1,2)-step competition graph is one of the generalizations and also is the key point of this paper.In 2011, Factor and Merz proposed the concepts of the (1,2)-step competition graph and (i, k)-step competition graph, characterized the (1,2)-step competition graphs of tour-naments and extended their results to the (i, k)-step competition graphs of tournaments. As (1,2)-step competition graph was put forward in 2011, related results are still little. In 2013, Xinhong Zhang and Ruijuan Li characterized the (i, k)-step competition graph of a round-digraph D and gave a sufficient and necessary condition for any two vertices in D to be adjacent in C1,2(D). In this paper, on the basis of the predecessors’results, the (1,2)-step competition graph of an extended tournament is characterized, and some sufficient condi-tions for the (1,2)-step competition graph of a strong round-digraph D to be hamiltonian are given.The thesis consists of three sections.In Chapter 1, we introduce the application background and the development of compe-tition graphs.In Chapter 2, we study the (1,2)-step competition graph of an extended tournament, and characterize the (1,2)-step competition graph of an extended tournament, and we obtain the following results:Let G is a (1,2)-step competition graph of extended tournament D=T[S1,S2,…,Si], if and only if G is the following graphs:1. Kn (l≠2); 2. Kcn (l=1); 3.Kn-|V(Dk)|∪K|V(Dk)|c(l>1); 4. Kn-E(K3) (l≥3); 5. Kn-E(P3[R1,r2,r3]) (l>2); 6. Kn-E(P2[R1,r2]) (l≠1), where R1 is a non empty set of isolated vertices in G, and r2,r3 are the vertices of G.In Chapter 3, we study the (1,2)-step competition graph of a strong round-digraph D, and we obtain the following results:The (1,2)-step competition graphs of 2-strong round-digraphs contain hamiltonian cycles and the (1,2)-step competition graphs of some 1-strong round-digraphs contain hamiltonian cycles.