Advances in Applied Mathematics
Vol.06 No.09(2017), Article ID:23171,5
pages
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
Received: Dec. 2nd, 2017; accepted: Dec. 19th, 2017; published: Dec. 26th, 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 , and is called the k-path vertex cover number of G. In this paper, we study some Cartesian products and give several estimations of .
Keywords:k-Path Vertex Cover, Cartesian Product Graphs, Estimated Value
几类笛卡尔乘积图的k路顶点覆盖数问题
李钊,左连翠*
天津师范大学数学科学学院,天津
收稿日期:2017年12月2日;录用日期:2017年12月19日;发布日期:2017年12月26日
摘 要
对于任意图 和正整数 ,如果图 中所有长度为 的路都至少含有其顶点子集 中的点,那么我们称顶点子集 为 路顶点覆盖集。我们定义最小的集合 的基数为 ,并且称它为图 的 路顶点覆盖数.本文我们主要研究了笛卡尔乘积图的 路顶点覆盖数问题,并给出了 的估计值。
关键词 : 路顶点覆盖,笛卡尔乘积图,估计值
Copyright © 2017 by authors and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
1. 引言
本文中我们研究的都是有限的、无向的、无环和无重边的图。我们用符号 和 去分别定义图 的顶点集和边集。对于任意的整数 ,我们用 去定义整数集 。 路顶点覆盖问题就是去找到最小的顶点集 使得图 中每个长度为 的路都至少包含 中的一个顶点 [1] 。我们定义最小的集合 的基数为 ,也被称为图 的 路顶点覆盖数。特别地,我们用长度来表示边数,用次序来表示顶点数。
路顶点覆盖问题的概念是首次由Novotný (2010)和Brešar et al. (2011)在研究无线电安全网络的连通问题上被引入的 [2] [3] 。涂建华在2011年的交通安全控制问题中也提及到 路顶点覆盖问题的概念 [4] [5] 。无线电传感网络的发展起源于军事应用并简记为WSNs。无论如何,WSNs现在多用于一些民用的设施,如环境的监控,家庭自动化装置和交通控制。无线电安全网络系统可以用图论的语言来表示其拓扑结构 [6] ,我们用顶点代表传感装置,用边来描述每对传感装置间传递的信号。我们关注 概括保护方案,它保证每两个无线设备间传输的数据的完整性。我们的方案假设在连通的网络中次序为 的传送路中至少有一个装置被保护 [7] 。本文我们主要研究几类关于圈和路的笛卡尔乘积图的最小的 路顶点覆盖数。
我们首先介绍几个数学符号及定义。对于实数 ,我们用 表示不超过 的最大整数,我们用 表示大于 的最小整数。图 和 的笛卡尔乘积图 具有顶点集 ,并且当 和 或者 和 时,顶点 和 间有连边。
最后本文内容安排为:第1节为引言;第2节为相关的引理;第3节介绍了 和 的笛卡尔乘积图的最小的 路顶点覆盖数的上界;第4节给出 和 的笛卡尔乘积图的最小的 路顶点覆盖数的下界和推论。
2. 相关的引理
引理2.1 [2] :对于正整数 , ,我们有
引理2.2:根据 路顶点覆盖的定义很显然有如下两个结论:
对于 的简单无向图 而言, 。
如果 是图 的一个子图并且 ,那么 。
证明:(1) 假设 是 的一个最小的 路顶点覆盖集, 是 的一个最小的 路顶点覆盖集,显然我们有 ,于是 。
(2) 假设 是 的一个 路顶点覆盖集, 是图 的一个子图,那么 是图 的一个 路顶点覆盖集,由于 ,于是 。
引理2.3:对于正整数 , ,我们有 。
3. 和 的笛卡尔乘积图的最小的k路顶点覆盖数的上界
在介绍定理3.1之前我们首先给出一个符号 的概念 [8] ,其中 为大于等于3的整数, 是 中小于等于 的最大元素, 是 中大于等于 的最小元素,这样我们称这组数对 为中间 对,很显然 并且使 的和尽可能的小。
定理3.1:如果 ,并且 为中间 对,我们有如下的式子
证明:首先我们构造一个最多有 顶点的 路顶点覆盖集去证明不等式的上界。让
并且
.
由于 中未被覆盖的最大连通子图同构于 ,于是我们可以很容易得出 是一个 路顶点覆盖集。
在 中我们覆盖了每一个第 个顶点和第 个顶点,由于有 层,所以 。同理,我们有 ,由于我们把每个交叉的位置处的顶点算了两次,而且 ,所以覆盖集 的大小为
.
同样的,我们也可以通过交换 和 的位置去构造一个有 个顶点的 路顶点覆盖集。这样我们就得到了 的上界。
4. 和 的笛卡尔乘积图的最小的k路顶点覆盖数的下界
定理4.1:对于正整数 ,我们有如下结论:
证明:首先在解决不等式下界的时候,我们先给出 的精确值。很容易可以得出 ,但是在本定理中我们考虑 。
如果正整数 ,我们有 。我们构造一个有4个顶点 路顶点覆盖集 ,去证明 。让 ,其中 。如果我们删去 中的点 并且删去它的关联边,于是我们得到了 中最大的未被覆盖的子图 并且 。于是 是 的 路顶点覆盖集,因此 。
很显然 ,由引理我们得到 。通过 的结构我们知道,我们至少需要一个顶点去覆盖每一个 层中的 路,无论这两层的顶点是否相连我们都定义它们为 ,我们可以知道 ,因此 。这样我们的等式 得到了证明。
下面我们基于上述面我们证明过的等式给出 的下界,我们可以把 分解成 个同构于 的不交子图,一个圈 (如图1所示),其中 和一个对于奇数来说的 。我们需要至少 个顶点去覆盖每一个同构于 的子图,需要至少 和 个顶点去分别覆盖子图 和 。因此对于奇数 言,
.
对于偶数 而言,我们把 分解成 个同构于 的不交子图和一个次序为 的圈 ,其中 , 。我们需要至少 个顶点去覆盖每一个同构于 的子图,需要至少 个顶点去覆盖子图 。因此有
Figure 1. A partition of for odd m
图1. 当m为奇数时, 的一个分解
.
.
证明:根据定理4.1的证明过程,我们可以把 分解成 个同构于 的不交子图和一个次序为 的圈 ,其中 , 。我们需要至少 个顶点去覆盖每一个同构于 的子图,需要至少 个顶点去覆盖子图 。因此有
文章引用
李 钊,左连翠. 几类笛卡尔乘积图的k路顶点覆盖数问题
The k-Path Vertex Cover in Several Cartesian Product Graphs[J]. 应用数学进展, 2017, 06(09): 1182-1186. http://dx.doi.org/10.12677/AAM.2017.69143
参考文献 (References)
- 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.
https://doi.org/10.1016/j.tcs.2016.04.043 - 2. Brešar, B., Kardoš, F., Katrenič, J. and Semanišin, G. (2011) Minimum k-Path Vertex Cover. Discrete Applied Mathematics, 159, 1189-1195.
https://doi.org/10.1016/j.dam.2011.04.008 - 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.
https://doi.org/10.1016/j.ipl.2014.06.018 - 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.
https://doi.org/10.1016/j.tcs.2011.09.013 - 6. Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Appli-cation. M. The Macmillan Press Ltd.
https://doi.org/10.1007/978-1-349-03521-2 - 7. Novotny, M. (2010) Design and Analysis of a Generalized Canvas Protocol. In: Proceedings of WISTP 2010, LNCS, Vol. 6033, Springer-Verlag, 106-121.
https://doi.org/10.1007/978-3-642-12368-9_8 - 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.
https://doi.org/10.1016/j.tcs.2011.09.009