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

The k-path vertex cover theory plays an important role in wireless sensor networks and traffic control fields.Over the past few years,the problems getting more and more attention.The vertex cover k-path problenm(VCPk)is that finding a minimum subset of vertices F so that each path of order k in G contains at least one vertex from F.The cardinality of a minimum k-path vertex cover is denoted by ?k(G),and is called the k-path vertex cover number of a graph G.In particular,we use the order of the a path P indicate the number of vertices on P while the number of the edges of P is abbreviated as the length of a path.The Cartesian product G?H of graphs G =(V(G),E(G))and H =(V(H),E(H))has the vertex set V(G)× V(H),and vertices(u1,v1)and(u2,v2)are adjacent whenever u1 = u2 and v1v2? E(G),or u1 u2 ? E(G)and v1=v2.The lexicographic product G o H of graphs G =(V(G),E(G))and H?(V(H),E(H))has the vertex set V(G)× V(H):and vertices(u1,v1)and(u2,v2)are adjacent whenever u1 u2? E(G),or u1 = u2 and v1v2 ? E(H).The strong product G(?)H of graphs G =(V(G),E(G))and H =(V(H),E(H))has the vertex set V(G)× V(H),and vertices(u1,v1)and(u2,v2)are adjacent whenever u1u2 ? E(G)and v1?v2,or u1 = u2 and v1v2 ? E(H),or u1u2 ? E(G)and v1v2 ?E(H).This articl mainly consists of four chapters:In the first chapter,we briefly introduce some preliminaries,the necessary symbols and the relative studying background of the k-path vertex cover.In the second chapter.we give the bound of the k-path vertex cover in Pm?Cn.Next,we get the exact values of ?k(Wn+1)through our lemma.Finally,we give the bound of the k-path vertex cover in the product graphs between Pm and Wn+1In the third chapter,we get the exact values of the k-path vertex cover in Km,n,.Meanwhile,under the inspiration of the exact values in ?k(Km,n),giving the estimate values in its cartesian products with P2.In the fourth chapter,we obtain the more precise upper bounds of ?k(Pm?Cn)and Pm(?)Cn with the lower bounds of ?k(Cm?Pn2).The conclusions obtained in this paper are new and can be validated by constructing k-path vertex cover set S with proper vertices.The cardinality of a minimum k-path vertex cover are given in each chapter to illustrate the accuracy and effectiveness of the obtained results.The obtained results provide fundamental basis for more complicate graphs.