The K-path Vertex Cover In Product Graphs And Complete Tripartite Graphs

The k-path vertex cover theory is widely used in wireless sensor networks and traffic control fields.In the recent years,more and more people have studied the approximate algorithm of k-path vertex cover problem and some results have been achieved.However,there is not much research on the k-path vertex cover problem on the product graphs,and there is still a lot of problems in this field.Therefore the paper discusses the problem of k-path vertex cover problem on some product graphs.For a graph G and a positive integer k,a subset S?(G)is called a k-path vertex cover if any path of order k in G contains at least one vertex from S.The cardinality of the minimum k-path vertex cover is called the k-path vertex cover number of graph G,denoted by Ψk(G).Based on the researching achievements of predecessors,we study the upper bound of the minimum k-path vertex cover number of some product graphs.By using proof by contradiction or the relevant Lemmas of subgraphs,the lower bound of the minimum k-path vertex cover number of these product graphs is studied.By using the principle of two side clipping,the exact values of the minimum k-path vertex cover number for some product graphs are obtained.The main research contents of the paper are as follows.The first chapter mainly introduces the research background and research status of the k-path vertex cover problem.The second chapter introduces some of the symbols,basic concepts and related lemmas in this paper.The third chapter discusses the minimum k-path vertex cover problem of the Cartesian product graphs in cycle graph and cycle graph,cycle graph and complete graph,cycle graph and complete bipartite graph.The upper and lower bounds of the k-path vertex cover number Ψk of the Cartesian product in cycle graph of length 3 and complete graph,cycle graph of length 3 and complete bipartite graph are obtained.Basis on this the upper and lower bounds of the Cartesian product in cycle graph of length m and complete graph,cycle graph of length m and complete bipartite graph are studied.The fourth chapter proves the minimum k-path vertex cover problem of the Cartesian product graphs in fan graph and bipartite graph,discusses the minimum k-path vertex cover number of fan graphs,and the upper and lower bounds of the minimum k-path vertex cover number in the Cartesian product of fan graph and complete bipartite graph.The fifth chapter discusses the minimum k-path vertex cover number of complete tripartite graph,extends the k-path vertex cover of the Cartesian product of 2-path and the complete tripartite graph to the m-path,then obtains the corresponding upper and lower bounds of Ψk.