几类笛卡尔乘积图的k路顶点覆盖数问题

对于任意图G和正整数k,如果图G中所有长度为k的路都至少含有其顶点子集S中的点,那么我们称顶点子集S为k路顶点覆盖集。我们定义最小的集合S的基数为φk(G),并且称它为图G的k路顶点覆盖数.本文我们主要研究了笛卡尔乘积图的k路顶点覆盖数问题,并给出了φk(Cm□PN2)的估计值。