The Path Covering Number Of Some Special Graphs And Regular Graphs

Graph theory has been developed rapidly in the recent 3 decades, which has been applied to computer science, physics, information theory, cybernetics, operational research, network theory etc. As an important concept in graph theory, Path covering problem is mainly used for parallel algorithm design, code optimization, application testing and ring protocol design. The present thesis focuses on the path covering problem about graphs.There is a very close relationship between the path covering number of connected graph and the that of the spanning trees. The study of the path covering problem of general connected graphs will be conducted through the analysis of the path covering number of the spanning tree. Therefore, exploring the path covering number of the tree-like graph is the basis of the study. Regular graph is one of the very important graphs. Studies on regular graph properties in graph theory is an enduring topic because of its very good symmetry. At the same time, it is also a very active field in graph theory research, so its path covering number should be more precise, and this paper will emphasis on the path covering problem of regular graph.The path covering of graph G is a set of paths which have no common vertex, keeping each vertex exactly on one of the paths. In all the path coverings of graph G, the path covering, which contains the least number of paths is called the minimal path covering of G, which is marked as P. And that whose number of path covering of G, is marked as P(G).Through discussing path covering numbers, this thesis gets such conclusions as follows:1. Starting from the path covering number of the graph, this thesis works out the change situation of path covering numbers when the connected graph loses an edge or a vertex and gives the minimal value of path covering number when k is an odd number and an even number respectively on the basis of studying path covering numbers of k complete binary tree T. Then this thesis conducts a study on the relation between path covering number of line graph and edge covering number of original graph, as well as the path covering number of the k-quasi regular graph T, analyzes the relation between path covering number of tree-like graph and the number of multiple edge in different ways, gives the value of path covering number with different number of multiple edge and finally investigates the necessary and sufficient conditions for 2-sparse trees.2. The essay written by Magnant and Martin got the upper bound of the path covering number of the simple k - (k≤5) regular graph. That is, the path covering number should fit: This thesis makes a further study and gets a more complete classification of simple k-(k≤4) regular graph when it gets the upper bound. That is, if graph G is k-regular graph with n vertices, the path covering number of graph G is if and only if G(?)tKk+1, where t is the connected component number of G.