L(j,k,l)-Labeling Algorithm For Random Graphs And Its Application In Frequency Allocation

As an interdisciplinary subject between computer science and mathematics,graph theory can transform many abstract and complex problems in the real world into graph theory problems by representing objects or phenomena as nodes and their connections as edges,displaying the topological structure of the relationships between things in a graphical form,and then solving real-world problems by studying the properties of graphs in depth.Therefore,graph theory is widely used not only in the real world but also in computer networks.Graph theory originated from mathematician Euler’s study of the Seven Bridges of K?nigsberg problem in 1736,and due to the rapid development of computers,it has also rapidly developed in modern times and has been widely used in path planning,frequency allocation,knowledge graph,exam seating arrangement,logistics problems,and scheduling problems,among others.Graph labeling is an important research point in the field of graph theory,originating from Rosa’s famous Graceful Tree Conjecture proposed in 1966.Because of the different mapping requirements,various graph labeling problems have emerged.There are many types of graph labeling,among which the more widely studied labeling problems are Graceful labeling,Magic labeling,Happy labeling,L(j,k)-labeling,etc.Graph labeling has been widely applied in many fields,such as frequency allocation,astronomy,database management,scheduling,and sharing schemes.Therefore,graph labeling has become a rapidly developing branch in the field of graph theory.Graph labeling allocates elements from the set of integers to the vertices and edges of a graph so that they satisfy certain conditions.Based on different conditions,scholars have gradually proposed and improved various concepts of labeling,established a series of graph labeling theories.The traditional method of labeling research is mainly based on the topological structure of the graph for combinatorial construction,manually labeling some special graphs such as cycle graphs,grid graphs,star graphs,fan graphs,bipartite graphs,etc.,and finding certain labeling rules.However,it is still difficult to accurately characterize and study the general random graphs and come up with accurate labeling rules.With the rapid development of computer science,using computer technology to design algorithms to solve graph labeling problems has become a new research method.The focus of this paper is the L(j,k,l)-labeling problem and its derived concepts.By designing algorithms to solve the graph labeling scheme of simple random connected graphs based on swarm intelligence and particle swarm optimization,we analyze the results and obtain some labeling theorems.The main work is as follows:(1)Introduce the relevant definitions and research background of graph theory and graph labeling and the specific concept of L(j,k,l)-labeling problem.(2)Design and implement an L(j,k,l)-labeling algorithm based on swarm intelligence and particle swarm optimization to solve random graphs,and use the algorithm to solve the L(3,2,1)-labeling and L(2,1,1)-labeling schemes of some special graphs such as tree graphs,single-double loop graphs,and random graphs within 16 points,obtain related labeling conclusions and provide specific proof processes.Based on the related conclusions and theorems within a finite number of points,we propose corresponding conjectures.By analyzing and organizing the experimental results,we propose a smaller upper bound conjecture for the L(3,2,1)-labeling and L(2,1,1)-labeling of general simple connected graphs:if the graph G is a random connected graph,then its L(3,2,1)-labeling number does not exceed(35)~3+1,then its L(2,1,1)-labeling number does not exceed(35)~2+2(35),(3)For the L(j,k,l)-edge labeling problem that maps to edges,we design an L(j,k,l)-edge labeling algorithm and conduct experiments to obtain some labeling data for 12205208 random graphs within 11 points,organize the data,and obtain some conclusions and conjectures.(4)By using the aforementioned L(j,k,l)-labeling theory and algorithm,a frequency allocation simulation experiment was conducted to provide specific frequency allocation schemes,and the correctness of the algorithm and its feasibility in frequency allocation problems were demonstrated through experiments.