Research On D(β)-vertex-sum-distinguishing Total Coloring Algorithms Of Random Graphs

Graph theory is an important branch of mathematics.It maps things of real life into graphs and solves practical problems through the study of them.At present,graph theory has been applied to many fields,such as transportation,the social network problems,knowledge graph and so on.Graph coloring originates from the four-color theorem,which is famous as one of the three major mathematics problems in modern times.It is a significant subject of graph theory research,which has a wide range of applications,such as examination room arrangement,class arrangement,transportation,dangerous goods storage,network communication,etc.There are plenty of the concepts about graph coloring,from the earliest vertex coloring,edge coloring,total coloring to subsequent vertex-distinguishing coloring,vertex-sum distinguishing coloring and so on.This paper is mainly about D(β)-vertex-sum-distinguishing total coloring,which is based on the concepts of Neighbor-vertex-sum-distinguishing total coloring and D(β)-vertex-distinguishing total coloring,and β represents the distance between veitices.When β=2 or β=3,the colorings are called D(2)-vertex-sum-distinguishing total coloring and D(3)-vertex-sum-distinguishing total coloring,respectively.In particular,whenβ=1,the coloring is Neighbor-vertex-sum-distinguishing,and when β=D(the diameter of the graph),it is Vertex-sum-distinguishing total coloring.Some corresponding algorithms are designed for the above colorings and the related problems are solved.The main contents are as follows:(1)The Neighbor-vertex-sum-distinguishing total coloring algorithm is designed and implemented,which is improved on the basics of the existing algorithm.According to the definition,the coloring conditions are converted into a series of processing functions,screening functions and judging functions in the algorithm.The algorithm uses the recursive backtracking to search in the solution space,and finally obtains the optimal solution of coloring through the step-by-step optimization method.Meanwhile,related coloring tests are carried out on the graphs within finite vertices.The existing conjectures are verified and new results are obtained as well.The algorithm is also basics of the design for subsequent coloring algorithms.(2)A new algorithm to solve the D(β)-vertex-sum-distinguishing total coloring of graphs is constructed and completed.In the design of the algorithm,parameters such as β and distance matrix are added,and the functions in the previous algorithm are reconstructed according to coloring conditions.The study of this paper is mainly concerning the results of D(2)-vertexsum-distinguishing total coloring and D(3)-vertex-sum-distinguishing total coloring for graphs with finite vertices.The algorithm is used to analyze and study the results and the relevant conclusions are given.For the trees,unicyclic graphs and bicyclic graphs,the size of the graphs are further expanded,meanwhile the algorithm is used to obtain more coloring results of these graphs,and the theorems and conjectures of a larger range of such graphs are given.(3)A Vertex-sum-distinguishing total coloring algorithm is designed and accomplished,which is used to color and analyze the graphs within finite vertices as well.Due to the complexity of the coloring,relevant conclusions are given and proved just for special graphs such as stars,fan graphs,wheel graphs,etc.