星图与二部图的某些乘积图上的k-路点覆盖

The k-path vertex cover in some products graphs of star graph and bipartite graph

对于一个点子集S■V(G),如果图G中任意一条k路上都有至少一个点来自于S,则称集合S是图G的一个k-路点覆盖。最小的k-路点覆盖集合的阶数为图G的k-路点覆盖数,记作ψ_(k)(G)。研究了星图与二部图的笛卡尔乘积图、字典积图和直乘积图上的k-路点覆盖问题,运用枚举法以及子图的相关概念,得到了它们的最小k-路点覆盖ψ_(k)(G)值的上、下界。

For a subset S■V(G),if any k-path contains at least one vertex from S,then it is called a k-path vertex cover set of the graph G.The minimum cardinality of k-path vertex cover set is called the k-path vertex cover number,which is denoted byψ_k(G).The k-path vertex cover problem is studied for Cartesian product graphs,lexicographic product graphs,directed product graphs of star graph and bipartite graph,and obtain an upper and a lower bound by enumeration and related concepts of subgraphs.