Antimagic Orientations Of Some Kinds Of Graphs

As an important branch of graph theory,the labeling of graphs has a long history.The coloring problem is a special labeling problem,which not only has an important theoretical value in graph theory,but also has a close relationship with many practical problems,such as the storage of chemical products,channel allocation of communi-cation system,the conflict of course arrangement in the course arrangement system of universities.The essence of labeling problem is a mapping from the vertex set or edge set of a graph to other set（here we consider integer set）.The antimagic labeling of undirected graph is a typical labeling problem,which is a special bijection from the edge set of a graph to an integer set.In recent years,whether there is antimagic labeling of undirected graph is a com-mon concern.In 1990,Hartsfield and Ringel proposed the concept of antimagic labeling of undirected graph and conjectured that every connected graph except K₂ is antimagic.With the deepening of the research on antimagic labelings of undirected graphs,Hefetz,M¨utze and Schwartz gave the concept of antimagic labeling of directed graphs in 2010（See Page 5）.They think that the study of antimagic labeling of directed graph need-s to consider the existence of antimagic orientations of every graph,and consider the conjecture:every connected graph has an antimagic orientation（See Section 1.2 for the definitions of antimagic labeling and antimagic orientation）.In order to verify the correctness of this conjecture for some kinds of graphs,in this paper,we give the characteristics and internal structure properties of graphs.With the help of the division of vertex sets,using mathematical induction method and the al-gorithm theory,we demonstrate the existence of antimagic orientations of disconnected even regular graphs and four kinds of connected graphs,respectively.This thesis is organized as follows.Chapter 1 is the introduction,which mainly introduces the related background knowledge of this paper,gives the basic definitions and preliminaries related to this thesis,and summarizes the main work and conclusions of this thesis.In Chapter 2,we give the properties and structural characteristics of the complete k-ary tree.According to the parity of k,we prove the conclusion that all complete k-ary trees have antimagic orientations for k=2t and k=2t+1（t≥1）,respectively.There-fore,we prove that the conjecture of every connected graph has antimagic orientation is true for the complete k-ary tree.In Chapter 3,we consider the antimagic orientations of three kinds of variants of complete binary tree,and solve the existence of the antimagic orientations of general-ized sibling trees,hypertrees and X-trees,respectively,and expand the family of graphs which support the conjecture.In Chapter 4,we improve the known conclusion about the existence of an antimagic orientation for a 2d-regular graph with at most two odd components.We obtained a sufficient condition for the existence of antimagic orientation for 2d-regular graph with k（k≥3）odd components,and prove the following two results:（1）When 3≤k≤5d+4,then there is an antimagic orientation of G;（2）When k≥5d+5 and the number of vertices of each odd components is at least 2·(（?）_{k-（5d+4）/（2d-2）（?）}+5,then there is antimagic orientation of G.In Chapter 5,we summary the thesis and give further research direction.