AAM  >> Vol. 6 No. 9 (December 2017)

    几类笛卡尔乘积图的k路顶点覆盖数问题
    The k-Path Vertex Cover in Several Cartesian Product Graphs

  • 全文下载: PDF(555KB) HTML   XML   PP.1182-1186   DOI: 10.12677/AAM.2017.69143  
  • 下载量: 531  浏览量: 2,044  

作者:  

李 钊,左连翠:天津师范大学数学科学学院,天津

关键词:
k路顶点覆盖笛卡尔乘积图估计值k-Path Vertex Cover Cartesian Product Graphs Estimated Value

摘要:

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

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(CmPN2).

1. 引言

本文中我们研究的都是有限的、无向的、无环和无重边的图。我们用符号 V ( G ) E ( G ) 去分别定义图 G 的顶点集和边集。对于任意的整数 a < b ,我们用 [ a , b ] 去定义整数集 { a , a + 1 , , b } k 路顶点覆盖问题就是去找到最小的顶点集 S 使得图 G 中每个长度为 k 的路都至少包含 S 中的一个顶点 [1] 。我们定义最小的集合 S 的基数为 φ k ( G ) ,也被称为图 G k 路顶点覆盖数。特别地,我们用长度来表示边数,用次序来表示顶点数。

k 路顶点覆盖问题的概念是首次由Novotný (2010)和Brešar et al. (2011)在研究无线电安全网络的连通问题上被引入的 [2] [3] 。涂建华在2011年的交通安全控制问题中也提及到 k 路顶点覆盖问题的概念 [4] [5] 。无线电传感网络的发展起源于军事应用并简记为WSNs。无论如何,WSNs现在多用于一些民用的设施,如环境的监控,家庭自动化装置和交通控制。无线电安全网络系统可以用图论的语言来表示其拓扑结构 [6] ,我们用顶点代表传感装置,用边来描述每对传感装置间传递的信号。我们关注 k 概括保护方案,它保证每两个无线设备间传输的数据的完整性。我们的方案假设在连通的网络中次序为 k 的传送路中至少有一个装置被保护 [7] 。本文我们主要研究几类关于圈和路的笛卡尔乘积图的最小的 k 路顶点覆盖数。

我们首先介绍几个数学符号及定义。对于实数 x ,我们用 x 表示不超过 x 的最大整数,我们用 x 表示大于 x 的最小整数。图 G = ( V ( G ) , E ( G ) ) H = ( V ( H ) , E ( H ) ) 的笛卡尔乘积图 G H 具有顶点集 V ( G ) × V ( H ) ,并且当 u 1 = u 2 v 1 v 2 E ( G ) 或者 u 1 u 2 E ( G ) v 1 = v 2 时,顶点 ( u 1 , v 1 ) ( u 2 , v 2 ) 间有连边。

最后本文内容安排为:第1节为引言;第2节为相关的引理;第3节介绍了 P m C n 的笛卡尔乘积图的最小的 k 路顶点覆盖数的上界;第4节给出 C m P n 2 的笛卡尔乘积图的最小的 k 路顶点覆盖数的下界和推论。

2. 相关的引理

引理2.1 [2] :对于正整数 k 2 n k ,我们有

φ k ( P n ) = n k , φ k ( C n ) = n k , φ k ( K n ) = n k + 1.

引理2.2:根据 k 路顶点覆盖的定义很显然有如下两个结论:

对于 2 k | V ( G ) | 的简单无向图 G 而言, φ k ( G ) φ k 1 ( G )

如果 G 是图 G 的一个子图并且 k 2 ,那么 φ k ( G ) φ k ( G )

证明:(1) 假设 S G 的一个最小的 k 路顶点覆盖集, S G 的一个最小的 k 路顶点覆盖集,显然我们有 | S | | S | ,于是 φ k ( G ) φ k 1 ( G )

(2) 假设 S G 的一个 k 路顶点覆盖集, G 是图 G 的一个子图,那么 S V ( G ) 是图 G 的一个 k 路顶点覆盖集,由于 | S V ( G ) | | S | ,于是 φ k ( G ) φ k ( G )

引理2.3:对于正整数 k 2 n k ,我们有 φ k ( P n 2 ) = 2 n k + 1

3. P m C n 的笛卡尔乘积图的最小的k路顶点覆盖数的上界

在介绍定理3.1之前我们首先给出一个符号 D i 的概念 [8] ,其中 i 为大于等于3的整数, a D i 中小于等于 i 的最大元素, D i 中大于等于 i 的最小元素,这样我们称这组数对 ( a , b ) 为中间 D i 对,很显然 a b = i 并且使 a + b 的和尽可能的小。

定理3.1:如果 k 4 ,并且 ( a , b ) 为中间 D i 对,我们有如下的式子

φ k ( P m C n ) min { m n a + 1 + n m b + 1 2 n a + 1 m b + 1 , m n b + 1 + n m a + 1 2 n b + 1 m a + 1 }

证明:首先我们构造一个最多有 m n a + 1 + n m b + 1 2 n a + 1 m b + 1 顶点的 k 路顶点覆盖集去证明不等式的上界。让

S 1 = { ( u i , v j ) P m C n | i [ 1 , m ] , j 0 ( mod ( a + 1 ) ) } { ( u i , v n ) P m C n | n }

并且

S 2 = { ( u i , v j ) P m C n | j [ 1 , m ] , i 0 ( mod ( b + 1 ) ) } .

由于 P m C n 中未被覆盖的最大连通子图同构于 P a P b ,于是我们可以很容易得出 S = ( S 1 S 2 ) \ ( S 1 S 2 ) 是一个 k 路顶点覆盖集。

C u i n 中我们覆盖了每一个第 a + 1 个顶点和第 n 个顶点,由于有 m 层,所以 | S 1 | = m n a + 1 。同理,我们有 | S 2 | = n m b + 1 ,由于我们把每个交叉的位置处的顶点算了两次,而且 | S 1 S 2 | = n a + 1 m b + 1 ,所以覆盖集 S 的大小为

| S | = m n a + 1 + n m b + 1 2 n a + 1 m b + 1 .

同样的,我们也可以通过交换 a b 的位置去构造一个有 m n b + 1 + n m a + 1 2 n b + 1 m a + 1 个顶点的 k 路顶点覆盖集。这样我们就得到了 φ k ( P m C n ) 的上界。

4. C m P n 2 的笛卡尔乘积图的最小的k路顶点覆盖数的下界

定理4.1:对于正整数 k 2 , n 4 ,我们有如下结论:

φ k ( C m P n 2 ) { 4 m 2 n k + 1 + ( m 1 ) ( n n k + 1 ) k + 2 n k + 1 , m 4 m 2 n k + 1 + ( m 1 ) ( n n k + 1 ) k , m

证明:首先在解决不等式下界的时候,我们先给出 φ k ( P 2 P k + 1 2 ) 的精确值。很容易可以得出 φ 2 ( P 2 P 3 2 ) = 5 ,但是在本定理中我们考虑 k 3

如果正整数 k 3 ,我们有 φ k ( P 2 P k + 1 2 ) = 4 。我们构造一个有4个顶点 k 路顶点覆盖集 S ,去证明 φ k ( P 2 P k + 1 2 ) 4 。让 S = { ( u 1 , v t ) , ( u 1 , v t + 1 ) , ( u 2 , v t ) , ( u 2 , v t + 1 ) } ,其中 t = k 2 。如果我们删去 S 中的点 ( u i , v j ) 并且删去它的关联边,于是我们得到了 P 2 P k + 1 2 中最大的未被覆盖的子图 P 2 P k 2 2 并且 V ( P 2 P k 2 2 ) = 2 k 2 k 1 。于是 S P 2 P k + 1 2 k 路顶点覆盖集,因此 φ k ( P 2 P k + 1 2 ) 4

很显然 C 2 k + 2 P 2 P k + 1 2 ,由引理我们得到 φ k ( P 2 P k + 1 2 ) φ k ( C 2 k + 2 ) = 3 。通过 P 2 P k + 1 2 的结构我们知道,我们至少需要一个顶点去覆盖每一个 P 2 层中的 k + 1 路,无论这两层的顶点是否相连我们都定义它们为 ( u i , v j ) , ( u p , v q ) ,我们可以知道 C 2 k P 2 P k + 1 2 \ { ( u i , v j ) , ( u p , v q ) } ,因此 φ k ( P 2 P k + 1 2 ) 2 + φ k ( C 2 k ) = 4 。这样我们的等式 φ k ( P 2 P k + 1 2 ) = 4 得到了证明。

下面我们基于上述面我们证明过的等式给出 φ k ( C m P n 2 ) 的下界,我们可以把 C m P n 2 分解成 m 2 n k + 1 个同构于 P 2 P k + 1 2 的不交子图,一个圈 C y (如图1所示),其中 y = ( m 1 ) ( n n k + 1 ) 和一个对于奇数来说的 P n 2 。我们需要至少 φ k ( P 2 P k + 1 2 ) 个顶点去覆盖每一个同构于 P 2 P k + 1 2 的子图,需要至少 φ k ( C Y ) φ k ( P n 2 ) 个顶点去分别覆盖子图 C y P n 2 。因此对于奇数 m 言,

φ k ( C m P n 2 ) 4 m 2 n k + 1 + ( m 1 ) ( n n k + 1 ) k + 2 n k + 1 .

对于偶数 m 而言,我们把 C m P n 2 分解成 x 个同构于 P 2 P k + 1 2 的不交子图和一个次序为 y 的圈 C y ,其中 x = m 2 n k + 1 y = ( m 1 ) ( n n k + 1 ) 。我们需要至少 φ k ( P 2 P k + 1 2 ) 个顶点去覆盖每一个同构于 P 2 P k + 1 2 的子图,需要至少 φ k ( C Y ) 个顶点去覆盖子图 C y 。因此有

Figure 1. A partition of C m P n 2 for odd m

图1. 当m为奇数时, C m P n 2 的一个分解

φ k ( C m P n 2 ) 4 m 2 n k + 1 + ( m 1 ) ( n n k + 1 ) k .

φ k ( C m P n 2 ) 4 m 2 n k + 1 + ( m n ( m 1 ) n k + 1 ) k .

证明:根据定理4.1的证明过程,我们可以把 C m P n 2 分解成 x 个同构于 P 2 P k + 1 2 的不交子图和一个次序为 y 的圈 C y ,其中 x = m 2 n k + 1 y = m n ( m 1 ) n k + 1 。我们需要至少 φ k ( P 2 P k + 1 2 ) 个顶点去覆盖每一个同构于 P 2 P k + 1 2 的子图,需要至少 ϕ k ( C Y ) 个顶点去覆盖子图 C y 。因此有

φ k ( C m P n 2 ) x φ k ( P 2 P k + 1 2 ) + y φ k ( C y ) = 4 x + y k = 4 m 2 n k + 1 + ( m n ( m 1 ) n k + 1 ) k .

文章引用:
李钊, 左连翠. 几类笛卡尔乘积图的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.
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