Font Size: a A A

The Investigation On The Crossing Numbers Of The Line Graphs And Some Classical Graphs

Posted on:2007-07-04Degree:DoctorType:Dissertation
Country:ChinaCandidate:T L ZhaoFull Text:PDF
GTID:1100360182988165Subject:Basic mathematics
Abstract/Summary:PDF Full Text Request
The crossing number of graphs is a very important concept in morden graph theory. Scince early in the 1950s, the Hungarian mathematician Paul Turan who suggest the actual problem, which named " Turan's brick factory problem " by Zarankiewicz, gradually being a very active field in the world. It attracts many graph theory expert to work.The research work in the crossing number of graph is not an important in theory,but also more practical, e.g. the circuit playout problems in VLSI and playout problems in electric circuit design, etc.. In 1983, Carey and Johnson proved that in general determining the crossing number of graphs is NP-complete. Because of its difficulty, At present the classes of graphs whose crossing numbers have been determined are very scarce, and there are only some special graphs whose crossing numbers are known. For example, these include the complete graph Kn for small n, the complete bipartite graph Km,n for small m and any n, the complete tripartite graph K1tm,n, some Cartesian product of two circuits, of path and stars , certain Petersen graphs, line graphs. If G be a nonplanar, Kulli and Beineke proved the necessary condition for which line graph has crossing number 1 in 1979, and, Jendrol' and Klesc have proved the necessary and sufficient conditions for which both the line graph and its primal planar graph have the same crossing number 1. The crossing number of the complete bipartite graphs Km,n, cr(Km,n), is true for the case m ≤ 6. It is an open problem to determine the crossing numbers of the graph Kn. In the 1980s, Asano havs proved the crossing numbers of K1,3,n and K2,3,n, since then no new results have been got.Firstly, we introduce the historical background and recent work on the crossing numbers of the graphs in some surface, and some relational concepts of crossing numbers.Secondly, in Chapter 2, we have presented some properties of the line graph and its primal planar graph ,and proved the necessary and sufficient conditions for which both the line graph and its primal graph have the same crossing number k(k ≥ 1):Let G be a graph with the crossing number k ≥ 1, and L(G) be its line graph.Then cr{L{G)) = k if and only if the following conditions hold:(1) A(G) < 4, and every vertex of degree 4 is a cut-vertex of G;(2) There exists a drawing of G in the plane with exactly k crossings in which each crossed edge is incident with a vertex of degree 2.The result extends essentially the work of Stanislav Jendrol' and Marian Klesc which the necessary and sufficient conditions for which both the line graph and its primal graph have the same crossing number 1.In Chapters 3, 4 and 5, We use the " local vertex's degree modified " and some combinatory mehtods, which differ to the known methods, to discuss the graphs ^i,4,n> -f^i,6,n >-K"i,7,n>-K'i,8,n and .#2,4,71 which crossing numbers are following:1. cr(KiAn) = n(n-l).2. If Zarankiewicz's conjecture is true for m — 7,then3. If Zarankiewicz's conjecture is true for m = 8,then4. If Zarankiewicz's conjecture is true for m < 9, then5. Let G be a complete tripartite graph /^2,4,ni then cr(G) = Z(6, n) + In.Finally, we intruduce the directions of our research work and put forward some problems which will be solved recently .
Keywords/Search Tags:Graphs, Line Graphs, Crossing numbers, Planar Graphs, Nonplanar graph, Drawing.
PDF Full Text Request
Related items