Short Cycle In Graphs And The Related Problems

Short cycle is an important structure in graphs.From chapter two to four of this paper we mainly introduce algorithms to find short cycles in varies graphs.In the second chapter,we introduce a algorithm to find all shortest paths between two vertices in a planar graph and prove that the shortest even cycle of geodesic in a connected planar graph G must be a fundamental cycle or the sum of two fundamental cycles.From the process of finding the shortest odd cycles in a connected planar graph G,we derive a conclusion that if the shortest odd cycle is the shortest cycle of the graph G,then one can find all the shortest odd cycles.Otherwise,we can only find one shortest odd cycle by taking advantage of a algorithm.In the third chapter,we investigate the shortest positive cycle and the shortest negative cycle in a signed graph under exceptional case.Using Breadth First Search algorithm,we finally conclude that if the length of the shortest positive(negative)cycle is longer than the length of the shortest negative(positive)cycle,then the shortest positive(negative)cycle is a basic cycle or the sum of two fundamental cycles.Thus we get that the shortest cycle in a signed graph is a basic cycle or the sum of two basic cycles.The forth chapter mainly studies the short cycle structure in a weighted graph.Based on the Dijkstra algorithm,we design a algorithm which can find a shortest even cycle in a weighted graph.In the fifth chapter of this paper,we use Euler formula and the critical-graphs methods of Gallai to show that the number of 7-color-critical graphs G on Sg is finite in a,simple way and prove that the number of vertices of G is at most 120(g-1)(g ? 2).Furthermore,we give an upper bound for the number of vertices of k-color-critical graphs(k ? 7)on orientable surfaces.