L(2,1)-labeling Algorithm Of Random Graph And Its Research In Frequency Assignment

As an extension of the graph coloring,the graph labeling has extremely high theoretical value.It has become one of the most popular directions in the field of graph theory research since proposed.In recent years,through the research of various labeling models,some of the gained results have been widely used in the fields of science,technology and engineering,which also has caused the graph labeling to attract more attention.Labeling models usually come from the topological relationships implicit in actual problems.Research on these models not only helps solve practical problems,but also promotes the development of graph theory itself.The graph labeling usually refers to assigning natural numbers to the vertices or edges of the graph to meet certain specific conditions.According to the different conditions,scholars have proposed the definitions of various labeling models and conducted in-depth research,which gradually forms a rich variety Icon sign theory.The traditional research method of labeling is mainly based on the topological structure of the graph itself and completed through combined construction method.But most of the graphs that can be processed are relatively special in this way,so it is not suitable for general random graphs.With the rapid development of computer science,it is a new research method and idea to design algorithms to solve various graph labeling of random graphs through computer technology.This paper mainly studies the L(2,1)-labeling and its variants related to channel frequency allocation.The algorithm is used to obtain the labeling results of non-isomorphic connected graphs within finite vertices.Through the analysis of experimental data,some results of several types of graphs are obtained about their labeling.The main work is as follows:(1)Introducing the concept of graphs and graph labeling,summarizing the current research status of L(2,1)-labeling and related variants,and analyzing the existing problems.(2)Designing and implementing the L(2,1)hybrid optimization labeling algorithm for random graphs.All simple connected graphs within 10 vertices were solved with L(2,1)-labeling,and the correct labeling results were obtained.After sorting and analyzing the experimental results,the relevant theorems within the finite vertices are drawn and corresponding guesses are put forward.Based on these guesses,the experimental scope is expanded,and the graphs with larger numbers of vertices(mainly including all unicyclic graphs within 16 vertices and some regular graphs)are verified.Focusing on Griggs’ conjecture about the upper bound of L(2,1)-labeling,this paper combines the experimental results to propose a smaller upper bound conjecture about irregular graphs: if the graph G is an irregular connected graph,then its L(2,1)-labeling number does not exceed 2Δ+1.The algorithm can only get the conclusion of the random graph within finite vertices.Obviously,it is not realistic to obtain all the data of graphs as the number of vertices increases,the graph structure becomes more complicated,and the number of graphs also explodes,so some joint graphs are definied to research,which combineswith the results of the algorithm and the combined construction method and some mathematical proofs are given of these graphs.It takes the advantages of the algorithm and the combined construction method totally.(3)Aiming at the problem of L(2,1)-edge labeling mapped to edges,two solving algorithms based on line graph and multi-objective optimization are designed.For the panchromatic L(2,1)-labeling is solved by using a heuristic search algorithm.The labelings of graphs within 9 vertices are obtained through experiments and some conclusions and guesses about tree graphs,unicyclic graphs and bicyclic graphs are sorted out.Among them,the conclusion of the edge labeling of the tree graph is the improvement of the known results.(4)Combining L(2,1)-labeling theory and algorithm,the frequency allocation simulation experiment is designed to illustrate its feasibility and application value.