| The graph coloring problem is one of the important research topics in graph theory,with a development history of more than 200 years.It covers a wide range of contents,including vertex coloring,edge coloring,total coloring,and various forms of extended coloring concepts.The team led by Professor Zhang Zhongfu proposed a series of new concepts such as adjacent vertex distinguishing edge coloring,adjacent vertex distinguishing total coloring,adjacent vertex reducible edge coloring and adjacent vertex reducible total coloring of graphs,which attracted the attention of some experts and scholars at home and abroad.This series of new concepts provide optimization strategies for solving practical problems such as discrete systems,combinatorial optimization,communication protocols,task scheduling and allocation.At the same time,the hot topic of graph labeling in combinatorial mathematics has always been high,which not only belongs to the field of graph theory but also to the category of design theory.Graph labeling refers to a mapping from the vertex set,edge set,or the union of the vertex set and edge set to a number set(usually positive integers);if the domain is the vertex set,it is called vertex labeling;if it is the edge set,it is called edge labeling;if it is the union of the vertex set and edge set,it is called total labeling.It has wide applications in communication network addressing,competition scheduling,and other fields.With the development of graph theory becoming increasingly mature,research on coloring problems related to "sum" is becoming more and more active.At the same time,distance coloring has also begun to enter the public’s field of vision.This paper combines distance coloring with reducible coloring,proposes two concepts related to distance coloring,and applies distance to labeling,proposing D(β)-reducible total coloring,D(β)-reducible total labeling,where β represents the distance between two vertices.Algorithms are designed to solve these three problems,and finite non-isomorphic connected graph coloring and labeling results are obtained through algorithms.At the same time,by analyzing experimental data,conclusions on reducible coloring and labeling of several types of graphs are obtained.We do the following works:(1)Introduce the concept of graphs and reducible coloring and labeling of graphs,introduce introduce the specific concept of vertices reducible total coloring with distance 2,D(β)-reducible total coloring,and D(β)-reducible total labeling.(2)Design and implement an algorithm vertices reducible total coloring with distance 2,solve simple connected graphs with up to 10 vertices and special graphs: double loop graphs,single loop graphs,and tree graphs,and obtain coloring results.After analyzing and studying the coloring results,relevant theorems within finite vertices are derived and corresponding conjectures are proposed,which are then verified by expanding the number of vertices(mainly including all single loop graphs,double loop graphs,tree graphs,and some complete bipartite graphs and regular graphs with up to 15 vertices).The conclusion of random graphs within finite vertices can be obtained through the algorithm,but as the number of vertices increases,the complexity of the graphs presented also increases,and the number of graph sets also explodes,which makes it difficult to run all the graph set data.Therefore,several types of connected graphs are defined,and relevant conclusions were given using combinatorial construction method based on the results of the existing algorithm.Mathematical proofs were also provided.(3)A D(β)-vertex reducible total coloring algorithm was designed and implemented.The algorithm used step-by-step optimization,performed preprocessing of the graph sets(divided the same degree point sets according to the distance definition),and then colored the graph sets according to the coloring rules.Finally,the coloring matrix and the maximum coloring number were obtained.The algorithm was executed to obtain the coloring results of isomorphic graphs with up to 10 vertices,which were displayed in tabular form.The results were analyzed,and several theorems of special graphs were derived,and corresponding proofs were given.(4)Designed and implemented the D(β)-vertex reducible total labeling algorithm,which improves on the original algorithm by adding a labeling process for vertices and introducing a distance condition: vertices of the same degree are partitioned based on the defined distance,and then labeled according to their labeling rules,with label values ranging from 1 to p +q.This algorithm was used to determine whether graph sets up to 10 vertices and special graphs satisfy the definition of D(β)-vertex reducible toal labeling. |
PDF Full Text Request