Research On Longest Path Intersection Problem For Some Graph Classes

The longest path of a graph is an important concept in graph theory and computer science.It refers to the simple path with the maximum length in a simple graph.The longest path of a graph is usually concerned by researchers together with the Hamiltonian path or Hamiltonian cycle of a graph.This thesis focuses on the longest path intersection problem of connected graphs,which is also known as the longest path Gallai conjecture.It is a famous open problem related to paths in graph theory.It discusses whether any number of longest paths on a given connected graph intersect at least one vertex.In this thesis,the longest path intersection problem on chordal graph,P5-free graph,split graph and cograph is researched.The main contributions are as follows.First,this thesis proves that the intersection of the longest paths on a connected P5-free graph and a connected chordal graph with maximum de-gree less than or equal to 4 is not empty.The intersection of the longest paths on a chordal graph is an open problem proposed by Balister in 2004.In the study of the longest path intersection problem of P5 graph and de-gree constrained chord graph,by analyzing the structural characteristics of longest path intersection on general graph,this thesis proposes for the first time to decompose the intersection of any number of longest paths into max-imal common subpaths set,and construct triangular cycle of longest path intersection by maximal common subpaths.Finally,the intersection trian-gle ring is used to prove that the intersection of the longest paths on the P5graph and the degree constrained chord graph is non-empty.In addition,in order to solve the problem of the intersection of the longest path on the connected chordal graph,a counterexample is given to falsifiate Balister’s conjecture that all vertices in Sm must be contained in L if the longest path L on the connected string graph passes through the minimum separator Sm in a graph.Secondly,a more concise proof of the intersection of all the longest paths on the split graph and the complementary graph is given.In this thesis,the structural characteristics of longest path intersection on split graph are described accurately by using clique tree representation and longest path property of split graph.In order to solve the problem of longest path of split graph,an approximate algorithm with approximate ratio of₄³is designed by applying the structural characteristics of longest path intersection of split graph.The thesis includes 25 figures,4 tables,and 123 references.