The K-path Vertex Cover Of Some Product Graphs

The k-path vertex cover theory has the most important role in wireless sensor net-works and traffic control fields.Over the past few years,the problems getting more and more attention.For a graph G and a positive integer k,a subset S of the vertex set of G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S.The cardinality of a minimum k-path vertex cover is called the k-path vertex cover number of a graph G,denoted by ?k(G).This paper mainly consists of four chapters:In chapter one,we introduce some preliminaries,the k path vertex and the relative studying background of the research status.In chapter two,we give some bounds and the exact values in special cases for?k(Pm?Kn)and ?k(PmoKn).In chapter three,we give the exact values of ?k(Sm?Kn),?k(SmoKn),?k(Sm(?)Kn),?k(Sm? Kn),and ?k(Sm×Kn),respectively.In chapter four,we give some lower bounds of ?k(Pm?Pn)and ?k(Pm?Pn2)for general m and n.