Path Covering Problem On Tree-like Graph And Its Application

In the past fifty years, graph theory has attracted much attention with the development of computer science and internet technology. As an important research field in graph the-ory, covering problem has many applications in the related fields, such as VLSI design, pro-gram testing, network, making a network with a Hamiltonian cycle and code optimization. In this thesis, we mainly investigate the path covering problem on tree-like graphs.For a graph G=(V, E) and a set of path P={P1, P2,…, Pr} where Pi= (Vi,Ei),1≤i≤r, if Vi∩Vj=(?), i≠j and∪'i=1 Vi= V, then the set P is a path covering of graph G. The path covering number of G, denoted by c(G), is the minimum cardinality of the path covering of G. The path covering problem is to find a path cover with c(G) paths.In the first part, we present the lower bound of tree is p-eh-1, where p is the num-ber of leaves and eh is the number of heavy edges. The heavy edges join two vertices with degrees greater than 2. In the second part, we obtain the relationship between block graph G and block-cutpoint-tree TG and give the exact values of the path covering numbers for a kind of block graphs and other tree-like graphs. Finally, we extend the application of the path cov-ering number for tree-like graphs to L(2,1)-labeling problem and Hamiltonian completion problem, and give the value of A(G), hole index p(G) and hc(G) for some special classes of graphs.