Research On Crossing Numbers And Some Other Problems In Graph Theory

As an important branch of discrete mathematics, graph theory has more than two hundred years history. It has been applied in many different fields in the modern world, such as physics, chemistry, communication technology, computer technology and social science etc. This paper researches on crossing numbers, path layer matrix and extremal problems, studies the related computer algorithms. Aided by computer algorithms and the mathematical proving techniques, some better results are obtained.The problem of crossing number comes out of the industrial practice. It has many applications in CAD. It is proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing numbers of very few families of graphs are known exactly. This paper researches on the crossing numbers. It improves the bounding conditions of an existed algorithm CNN, calculates the crossing numbers of P(n, k) for n≤16 and the crossing numbers of C(n;{1,k}) for n≤18. According to the good drawings constructed by the algorithm, it gives the upper bounds of cr(P(4k+2,2k)) and cr(P(4k+2,4)) for k≥3, the upper bounds of cr(P(mk, k)) for k≥3 and m≥4, the upper bounds of cr(C(mk;{1,k})) for k≥3 and m≥4, the upper bounds of cr(C(n;{1,|_n/2-1_|})) for odd n≥13. It designs several different grouping methods and different crossing grouping functions according to the graphs, determines the crossing numbers of C(n;{1,3}) for n≥8, C(3k;{1,k}) for k≥3 and C(n;{1 ,n/2-1}) for even n≥8 successfully.The problem of the path layer matrix comes out of the medical analyses and is closely related to the problem of graph isomorphism. It is asserted that an equality of the path layer matrices for graphs of order n≤11 is a sufficient condition for their isomorphism. This paper proposes a new method to study the path layer matrix. It constructs the basic graphs which have some certain properties by computer, and connects the four copies of the same basic graph into a pair of non-isomorphic graphs which have the same path layer matrix. The method is proved mathematically in this paper. It also designs the algorithm constructing the r-regular basic graphs, then constructs a 4-regular basic graph of 9 vertices, further a pair of non-isomorphic 4-regular graphs which have the same path layer matrix and 18 vertices are obtained. Hence the upper bounds of f(4), which is the minimal order of a pair of non-isomorphic 4-regular graphs having the same path layer matrix, is improved to be 18, and the upper bound of f2, which is the minimal order of a pair of non-isomorphic graphs having the same path layer matrix without cut vertices, is improved to be 18. i.e. f(4)≤18, f2≤18.Extremal problem is one of the core parts of the graph theory. The extremal problems for that the forbidden subgraphs are polygons are typical. This paper studies the extremal graphs which contain no 3-cycles, 4-cycles or 5-cycles. It gives ex(n;{C3,C4,C5}) for 1≤n≤42. It alsodesigns an algorithm to construct the critical graphs, thereby constructs all the extremal graphs not containing 3-cycles, 4-cycles or 5-cycles for 1≤n≤42. For n>42, the upper bound of ex(n; {C3, C4, C5}) is given.