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

Advances in Applied Mathematics 应用数学进展, 2017, 6(9), 1182-1186 Published Online December 2017 in Hans. /journal/aam /10.12677/aam.2017.69143 The k-Path Vertex Cover in Several Cartesian Product Graphs Zhao Li, Liancui Zuo* College of Mathematical Science, Tianjin Normal University, Tianjin nd th th Received: Dec. 2 , 2017; accepted: Dec. 19 , 2017; published: Dec. 26 , 2017 Abstract 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 ϕ G , and is called the k-path vertex cover number of G. In this paper, we study some Cartesian k ( ) 2 products and give several estimations of ϕ C P . k ( m n ) Keywords k-Path Vertex Cover, Cartesian Product Graphs, Estimated Value 几类笛卡尔乘积图的k路顶点覆盖数问题 李 钊，左连翠* 天津师范大学数学科学学院，天津 收稿日期：2017年12月2 日；录用日期：2017年12月19 日；发布日期：2017年12月26 日 摘 要 G k G k S 对于任意图 和正整数 ，如果图 中所有长度为 的路都至少含有其顶点子集 中的点，那么我们称 S k S ϕ G G k 顶点子集 为 路顶点覆盖集。我们定义最小的集合 的基数为 k ( )，并且称它为图 的 路顶点覆 k 2 盖数.本文我们主要研究了笛卡尔乘积图的 路顶点覆盖数问题，并给出了ϕ C P 的估计值。 k ( m n ) *通讯作者。 文章引用: 李钊, 左连翠. 几类笛卡尔乘积图的k 路顶点覆盖数问题[J]. 应用数学进展, 2017, 6(9): 1182-1186.