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

The k-Path Vertex Cover in Several Cartesian Product Graphs

作　　者：李钊 左连翠[1] 

机构地区：[1]天津师范大学数学科学学院,天津

出　　处：《应用数学进展》2017年第9期1182-1186,共5页Advances in Applied Mathematics

摘　　要：对于任意图G和正整数k,如果图G中所有长度为k的路都至少含有其顶点子集S中的点,那么我们称顶点子集S为k路顶点覆盖集。我们定义最小的集合S的基数为φk(G),并且称它为图G的k路顶点覆盖数.本文我们主要研究了笛卡尔乘积图的k路顶点覆盖数问题,并给出了φk(Cm□PN2)的估计值。For a graph G and a positive integer k, a subset S of vertices of G is called a k-path vertex cover if S intersects all paths of order k in G. The cardinality of a minimum k-path vertex cover is denoted by φk(G), and is called the k-path vertex cover number of G. In this paper, we study some Cartesian products and give several estimations of φk(Cm□PN2).

关 键 词：k路顶点覆盖 笛卡尔乘积图 估计值 

分 类 号：O1[理学—数学]