Long Cycles In Graphs And The Structure Of Longest Cycle Bases

Generally speaking, the study of long cycles in a graph develops along two routs. The old way is called "Large degree sums" condition for those having too many edges(i.e., dense graphs), so that they are almost "complete". Among which the Fan-condition is the most famous. One has been cited more than 10000 times in various papers. Since there is no breaking-through points, the dense graph conditions are seldom applied. The other direction is the sparse-graph conditions designed for those having some particular backgrounds. For instance, a main stream of sparse-graphs is concentrated on embedded graph on surfaces. Its land-mark was founded by H.Whitney and W.Tutte in 1930s-1940s. Now by using 2-manifold way to investigate long cycles has become one of main tools in the study of long cycles.In this thesis, we try to study the long cycle from a new view—long cycle bases in a graph. Intuitively, some basic information should be contained in a long cycle base. Our results show that many properties on long cycle are contained in long cycle bases. Based on a Hall-type condition for bases transformation, we obtain a sufficient and necessary condition for a base to be longest one. Furthermore, we show that all the long cycle bases have the same structures, i.e., there exists a 1-1 correspondence between any two longest bases. Moreover, any two maximum cycle bases have the same number of k-cycle, 3≤k≤n . And then, we obtain the cycle bases structures of wheel graph and complete graph.