The Study Of The Anti-magical Conjecture Of The Graph

Graph theory is an important branch of discrete mathematics,combining the knowledge of the other subjects,such as group theory,matrix theory,probability theory,topology and so on.It has an widespread application in the fields of chemistry,physics,astronomy,geography,biology,computer science and the like.The problems of graph antimagic labeling stems from the two conjectures raised by Hartsfield and Ringel in 1990,which are 1.Every connected graph different from K2 is antimagic;2.Every tree different from K2 is antimagic.The edge labeling of graph G =(V,E)is a bijective that maps the edge set into integer set,that is ?:E?{1,2,…,|E|}.For each vertex u of G,the vertex-sum at u is defined as f?(u)=?e?E(u)?(e),where E(u)is the set of edges incident to u.A graph is called antimagic if there exists a edge labeling such that the sums of the labels on the edges incident to each vertex are distinct,that is to say for edge labeling ?,f?(u)?f?(v)for any two distinct vertices u,v?V(G).The above two conjectures no sooner raised than received much attention around the world and many results are obtained.The antimagicness of many special graphs are proved,such as paths,cycles,wheels,stars,double stars,fans,join graphs,complete graphs,the cubic graphs,dense graphs,regular graphs,odd regular graphs,regular bipartite graphs,trees,lattice grids and prisms,the Cartesian product of graphs,the planar graphs,the generalized pyramid graphs,the directed graphs and so on.The conjectures had not yet completely solved and remained largely open.The antimagic labeling of graphs have applied good in computer network theory,for example,require unbalanced loading:consider a supply of routers of distinct capacities with which to build a network,then an antimagic labeling of the edges would represent bandwidth capacity between routers.In this paper,we mainly researched the two antimagic labeling problems which are the graph of lexicographic products and the amalgamation graphs.We used the matrix to label the complete bipartite subgraphs and adopted the ways of modifications to solve the conflicts which are the two different vertices have the same vertex-sum.And finally,we gained that the lexicographic product of two paths and the amalgamation of the two complete graphs are antimagic.The results which obtained in this paper are compensations in the field of antimagic labeling of graphs,in the meantime it improved,extended and unified the latest researches which gained by many scholars.The paper has four parts:the first one is introduction.In this section,we introduced the history of graphs,the background of selected topic,the research status and the basic conceptions.In the second part,we studied the antimagicness of the lexicographic product of two paths.Firstly,we introduced the conception of the lexicographic product and the labeling techniques of the lexicographic product of two paths,the next is to show the six claims which gained in the process of labeling,after that we raised the ways of modification to solve the conflicts which belong to vertex-sum,at the end we've proved that the lexicographic product of two paths is antimagic by categorized discussion method.In the third part,we study the amalgamation of two complete graphs is antimagic.First of all,we introduced the conception of the amalgamation graph and labeled edges by the constructed special block matrix which the leading diagonal are zeros,the next is proved the amalgamation graph of two complete graphs is antimagic.In the last part is summary and expectation.In this part,we obtained the conclusion that the lexicographic product of two paths and the amalgamation of two complete graphs are antimagic,and looking forward to the future work which we will solved,such as proved the antimagicness of Spider,Halin,the biregular graphs,biregular bipartite graphs.