几类笛卡尔乘积图的k路顶点覆盖数问题
The k-Path Vertex Cover in Several Cartesian Product Graphs
DOI: 10.12677/AAM.2017.69143, PDF,   
作者: 李 钊, 左连翠：天津师范大学数学科学学院，天津
关键词: k路顶点覆盖；笛卡尔乘积图；估计值；k-Path Vertex Cover； Cartesian Product Graphs； Estimated Value
摘要: 对于任意图G和正整数k，如果图G中所有长度为k的路都至少含有其顶点子集S中的点，那么我们称顶点子集S为k路顶点覆盖集。我们定义最小的集合S的基数为φk(G)，并且称它为图G的k路顶点覆盖数.本文我们主要研究了笛卡尔乘积图的k路顶点覆盖数问题，并给出了φk(Cm□PN2)的估计值。
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 φ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路顶点覆盖数问题[J]. 应用数学进展, 2017, 6(9): 1182-1186. https://doi.org/10.12677/AAM.2017.69143

参考文献

[1] Xiao, M.Y. and Kou, S.W. (2017) Exact Algorithms for the Maximum Dissociation Set and Minimum 3-Path Vertex Cover problems. Theoretical Computer Science, 657, 86-97.
[Google Scholar] [CrossRef] 
[2] Brešar, B., Kardoš, F., Katrenič, J. and Semanišin, G. (2011) Minimum k-Path Vertex Cover. Discrete Applied Mathematics, 159, 1189-1195.
[Google Scholar] [CrossRef] 
[3] Novotný, M. (2010) Design and Analysis of a Generalized Canvas Protocol, Information Security Theory and Practices. Security and Privacy of Pervasive Systems and Smart Devices, 6033, Springer, 106-121.
[4] Tu, J. (2015) A Fixed-Parameter Algorithm for the Vertex Cover Problem. Information Processing Letters, 115, 96-99.
[Google Scholar] [CrossRef] 
[5] Tu, J.H. and Zhou, W.L. (2011) A Primal-Dual Approximation Algorithm for the Vertex Cover P3 Problem. Theoretical Computer Science, 412, 7044-7048.
[Google Scholar] [CrossRef] 
[6] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Appli-cation. M. The Macmillan Press Ltd.
[Google Scholar] [CrossRef] 
[7] Novotny, M. (2010) Design and Analysis of a Generalized Canvas Protocol. In: Proceedings of WISTP 2010, LNCS, Vol. 6033, Springer-Verlag, 106-121.
[Google Scholar] [CrossRef] 
[8] Kardoš, F., Katrenič, J. and Schiermeyer, I. (2011) On Com-puting the Minimum 3-Path Vertex Cover and Dissociation Number of Graphs. Theoretical Computer Science, 412, 7009-7017.
[Google Scholar] [CrossRef] 

为你推荐