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.