Distance Labeling Of Graphs And Its Applications In Mechanical Calculation

Graph theory is an important branch in discrete mathematics. The problem of labeling graph is one of the important field of study in graph theory, which is widely used in the field of science and technology and engineering. Distance labeling of graph is a very active research field in the past 30 years, which originally comes from the study of the frequency assignment problem, and also is an generalized coloring problem of graph, with a certain theoretical research value and practical value.An L ( k1 , k 2, , k p)- labeling of any simple graph G = (V ,E) is a mapping: f : V (G )→{0,1,2, , k} such that the labels assigned to any two vetices x, y which is distant i (≤p) differ by at least k i, where k1 , k 2, , k p are non-negative integers. We also call this class of labeling the distance p labeling, or simply the distance labeling. The small k for which an L ( k1 , k 2, , k p)- labeling of a graph G exists is called L ( k1 , k 2, , k p)- labeling number, and denoted byλ(G ; k1 , k 2, , kp) or 1 , 2, , ( )λk k k pG. If x, y are any two edges of G , then we can easily define the distance edge labeling by adding an"edge"in the above definition.The theory of distance labeling of graphs can be applied in mechanical calculation. Finite element method (FEM) is the important tool in mechanical calculation. Finite element nodal ordering is one of the important step in FEM, which has a significant effect on computation. Based on the viewpoint of graph theory, finite element nodal ordering is essentially the distance labeling of graph. We can optimize finite element nodal ordering using graph theory.Distance labeling of graphs has been studied for nearly 30 years since it had been proposed, and many results have been made. Most of the results focus on the L (2,1)-labeling and L ( h, k )-labeling, while there are not many results about the distance p labeling with p≥3. However, recently, as more and more scholars begin to study the distance p labeling with p≥3, it is becoming a hot spot of present research.This dissertation focus on theory and application of distance labeling of graph, including L ( h, k )-labeling, L ( h, 2,1)-labeing and L ( h, 1, ,1)-labeling of general graphs, trees, infinite regular grids and outerplanar graphs, and also its applications in mechanical calculation. The dissertation includes six parts and the main points of each part are as follows:The first part introduced the basic definitons and notations of graphs, the research background, development nowadays, applications in engineering of distance labeling, and also the main work and conclusions of the thesis. In the second part, the L ( h, k )-labeling and L ( h , k )-labeling were studied. It mainly included:1) TheΔ2-conjecture proposed by Griggs and Yeh is one of the famous problem in this field, and the problem is still not solved thoroughly. By given the L (2,1)-labeling numbers of total graphs, skew product graphs, converse skew product graphs and cartesian sum of graphs, which all improves the results available, we partially proved that the conjecture is ture for these class of graphs.2) The L ( h , k )-labeling of outerplanar graphs were studied and L ( h , k )-labeling numbers were given, which partially improve some known results.3) The L ( h , k )-edge labeling of graphs were studied. Some properties of L ( h, k )- edge labeling were presented. The L ( h, 1)-edge labeling numbers of general graphs were obtained based on one L ( h, 1)-edge labeling algorithm, and the results generalize and improve the known results. Additionally, one upper bound of L ( h, k )-edge labeling numbers of outerplanar graphs were also give.In part three, research had focused on the L ( h, 2,1)-labeling of general graphs, trees, infinite regular grids, chordal graphs, t-trees, outerplanar graphs and total graphs. The main results were:1) Some properties of L ( h, 2,1)- labeling on general graphs were presented. A upper bound of the L ( h, 2,1)- labeling numbers of general graphs were obtained based on one L ( h, 2,1)- labeling algorithm, and a lower bound were also given. And besides, relations between L ( h, 2,1)- labeling numbers and the perfect matching, Hamiltonian property of graphs were discussed.2) The upper and lower bounds of L ( h, 2,1)-labeling numbers of trees were presented, which are both attainable. In addition, an algorithm on L ( h, 2,1)-labeling the infinite regular trees is proposed.3) The L ( h, 2,1)-labeling of four classes of infinite regular grids were studied. The exact value of L ( h, 2,1)-labeling numbers were obtained in most cases, while the upper and lower bounds were given in other cases. And in all cases, an algorithm on L ( h, 2,1)-labeling each of the infinite regular grid was proposed.4) The L ( h, 2,1)-labeling of chordal graphs, t-trees, outerplanar graphs and total graphs were studied and L ( h, 2,1)-labeling numbers were given. Also, the exact value of L (3,2,1)-labeling number of total graphs of paths were obtained. In part four, research was centred on the L ( h, 1, ,1)-labeling of general graphs, trees and infinite regular grids. The main results were:1) Some properties of L ( h, 1, ,1)- labeling on general graphs were presented. Relations between the one-to-one L ( h ,1, ,1)- labeling numbers and the perfect matching, Hamiltonian property of graphs were discussed. A upper bound of the L ( h, 1,1)- labeling numbers of general graphs were obtained based on one L ( h ,1,1)- labeling algorithm, and a lower bound were also given.2) The upper and lower bounds of L ( h, 1,1)-labeling numbers of trees were given, which improved the known resuls and were both attainable. The exact value of L ( h, 1,1)-labeling numbers of infinite regular trees and caterpillar trees were presented. Moreover, L (1, ,1)-labeling numbers of general trees were proposed, and the exact value for infinite regular trees were obtained.3) The exact values of L ( h ,1,1)-labeling numbers of infinite hexagonal and octagonal regular grids were obtained, while the upper and lower bounds of infinite triangular regular grids were also presented. Additionally, the L ( h ,1, ,1)-labeling of infinite octagonal regular grids were studied. The exact values of labeling number were obtained in most cases; only in a small iintreval the different upper and lower bounds were given.The focus of the fifth part was the applications of distance labeling of graph in mechanical calculation. It mainly included:1) Finite element method is the important tool in mechanical calculation. It is redescribed the finite element nodal ordering problem with graph theory.2) Based on the anslysis of several bandwidth optimization methods for finite element nodal ordering using graph theory, a new optimization method was presented, which was simple, easible and effective at the bandwidth optimization.The last part was the conclusions and prospects.There are 18 figures and 130 references in total.