Research On Magic Total Labeling And Anti-magic Vertex Labeling Algorithms Of Random Graphs

This thesis mainly investigates the two most classic labelings in the graph labeling area,namely the edge magic total labeling and(a,d)-edge-antimagic vertex labeling.Firstly,for graph G(p,q),if there is a mapping f:V(G)U E(G)?{1,2,…,p+q},so that every edge uv E E(G)satisfies f(u)+f(v)+f(uv)=K,K is a constant,then the graph G(p,q)is the edge magic total labeling graph.In particular,if the vertex labels of the graph G satisfy:f(V(G))?{1,2…,p},then f is called super edge magic sum total label of G,and G is the super edge magic sum total label graph.Up to now,most researchers have focused on special graphs such as Cn,Km,n fans,binary trees,caterpillars,etc.The special graphs mentioned above are not enough to reflect many complex problems in the real world,so in this paper,a new edge magic total labeling algorithm is designed to finish the labelings of random graphs,and the labeling results of all the unicyclic graphs with less than 16 vertices are obtained.By analyzing the algorithm results,the rules of two unique unicyclic graphs are obtained,and related theorems are given and proved.Finally,the results show that all the unicyclic graphs with less than or equal to 16 vertices have edge-magic total labeling,and most of them are super edge-magic total labeling.Therefore,it is speculated that the unicyclic graphs with more than 16 vertices also have the same characters.Secondly,the edge-magic total labeling algorithm are used to obtain the labelings of three types of combination graph within finite point,which is composed by fan graph,circle graph and star graph.And the edge-magic total labeling accurate algorithm of three types of graph with infinite vertices is obtained by combining the obtained graph labels with combinatorial construction method.At the end,an(a,d)-edge-antimagic vertex labeling of a graph with p vertices and q edges is a one to one mapping taking the vertices onto the integers {1,2,…,p},so that the set of edge-weights of the graph is {a,a+d,…,a+(q-1)d},where a and d are two positive integers,and the weight of the edge is equal to the label sum of its corresponding two vertices.This definition was proposed in 2000 by Simanjuntak,Bertault and Miller,etc.And They got the following extraordinary graph conclusions including C2n,C2n+1,P2n and Pn.Later,many scholars also started to study this type of graph labeling and got the relevant conclusions about special graphs,such as Wn,Kn,Kn,n,C3(n),mCn and so on.These graphs are just a small part of all the atlas,for which it is of extraordinary significance to solve the labelings of the remaining general graphs.In this paper,an algorithm is proposed to solve the(a,d)-edge-antimagic vertex labeling of simple connected graphs within finite vertices.According to the algorithm results,some precise algorithms for special graphs and composite graphs are obtained,and a heuristic search algorithm model is given for general graphs.The algorithm can be divided into two parts,one is the pretreat function,which is set based on the definition,pretreat all the graphs in the atlas and exclude non-(a,d)-edge-antimagic vertex labeling graphs;the other one is to obtain the(a,d)-edge-antimagic vertex labeling of remaining graphs.In particular,it is known that when q?p,graphs G(p,q)have no(a,2)-edge-antimagic vertex labeling through the pretreat function.Therefore,studying the graph of q<p is enough.Here,(a,2)-edge-antimagic vertex labeling of all tree graphs within 13 vertices can be obtained through the algorithm.