Diagram Of The Entire Spectrum Of The Theory Of Solution Of The Computer Search

This thesis contributes to the theory of integral graphs and computer searching of the solutions for some characteristic polynomials of graphs. From Chapter 2 to Chapter 5, some new families of integral trees with diameters 4. 5, 6 and 8 are characterized by making use theory of number and computer searching. Some methods of costructing integral graphs are obtained in Chapter 6. In Chapter 7, we give a useful sufficient and necessary condition for complete r-partite graphs to be integral, from which we can construct infinite many new classes of such integral graphs. In the last chapter, Chapter 8. we prove some classes of regular graphs are not only integral but also Laplacian integral. We also give the numbers of spanning trees for such graphs.The termnology and notations can be found in the first chapter. At the same time, we give a brief introduction of the main results of the thesis.In Chapter 2, some new families of integral trees with diameters 4 and 6 are constructed by identifying the centers of two trees. All these classes are infinite. They are different from those in existing literatures. This is a new contribution to the search of integral trees. We believe that it is useful for constructing other integral trees.In Chapter 3, some new families of integral trees with diameters 4, 6 and 8 are given. All these classes are infinite. They are different from those in existing literatures. We also prove that the problem of finding integral trees of diameters 4. 6 and 8 is equivalent to the problem of solving Diophantine equations. We believe that it is useful for constructing other integral trees. To our knowledge, P. Hic and R. Nedela proved firstly that there are infinitely many balanced integral trees of diameter 8 in 1998. In fact, we also prove independently this result by using a different method, and these integral trees of diameter 8 are different, from their results.In Chapter 4, some new families of integral trees with diameters 4, 6 and 8 are given by making use theory of number and computer searching. Most of these classes are infinite. They are different from those in existing" literatures. This is a new contribution to the search of integral trees. We believe that it is useful for constructing other integral trees. Finally, we propose several basicopen problems on integral trees for further study.In Chapter 5, some new families of integral trees with diameters o and G are constructed by making use theory of number and computer searching. All these classes are infinite. They are different from those in existing literature. We also prove that the problem of finding integral trees of diameters 5 and 6 is equivalent to the problem of solving some Diophantine equations. The discovery of these integral trees is a new contribution to the search of such trees.In Chapter 6, some new classes of integral graphs are given by two new ways. We also prove that the problem of finding such integral graphs is equivalent to the problem of solving Diophantine equations. Some classes are infinite. The discovery of these classes is a new contribution to the search of such integral graphs.In Chapter 7. we give a useful sufficient and necessary condition for complete r-partite graphs to be integral, from which we can construct infinite many new classes of such integral graphs. The discovery of these integral complete /■-partite graphs is a new contribution to the search of such integral graphs. In fact, M. Roitman's result on the integral complete tripartite graphs is generalized in this chapter (see also M. Roitman. An infinite family of integral graphs, Discrete. Math. 52(2-3)(1984), 313-315. MR 86a:05089). Finally, we propose several basic open problems for further study.In Chapter 8, let KV[KP^\] denote the (p - l)-regular graph with p(p — I) vertices. We shall give its spectra and characteristic polynomial from the theory on matrices. In fact, a result of F. Harary and A.J. Schwenk on a regular integral graph is generalized in this chapter. We derive the characteristic polynomials for its complement graph, its line graph, the complement graph of its line graph and the line graph of its complement graph. We also obtain the numbers of spanning trees for such graphs. We also prove these graphs are not only integral but also Laplacian integral. The discovery of these1 integral graphs is a new contribution to the search of integral graphs.