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

The k-Path Vertex Cover in Several Cartesian Product Graphs

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

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(C_m□P_N²).

1. 引言

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

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

我们首先介绍几个数学符号及定义。对于实数 $x$ ，我们用 $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数，我们用 $\lceil x\rceil$ 表示大于 $x$ 的最小整数。图 $G=\left(V\left(G\right),E\left(G\right)\right)$ 和 $H=\left(V\left(H\right),E\left(H\right)\right)$ 的笛卡尔乘积图 $G\square H$ 具有顶点集 $V\left(G\right)\times V\left(H\right)$ ，并且当 $u_1=u_2$ 和 $v_1{v}_2\in E\left(G\right)$ 或者 $u_1{u}_2\in E\left(G\right)$ 和 $v_1=v_2$ 时，顶点 $\left(u_1,v_1\right)$ 和 $\left(u_2,v_2\right)$ 间有连边。

最后本文内容安排为：第1节为引言；第2节为相关的引理；第3节介绍了 $P_m$ 和 $C_n$ 的笛卡尔乘积图的最小的 $k$ 路顶点覆盖数的上界；第4节给出 $C_m$ 和 $P_n^2$ 的笛卡尔乘积图的最小的 $k$ 路顶点覆盖数的下界和推论。

2. 相关的引理

引理2.1 [2] ：对于正整数 $k\ge 2$ ， $n\ge k$ ，我们有

$\begin{array}{l}{\phi }_k\left(P_n\right)=\lfloor \frac{n}{k}\rfloor ,\\ {\phi }_k\left(C_n\right)=\lceil \frac{n}{k}\rceil ,\\ {\phi }_k\left(K_n\right)=n-k+1.\end{array}$

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

对于 $2\le k\le \left|V\left(G\right)\right|$ 的简单无向图 $G$ 而言， ${\phi }_k\left(G\right)\le {\phi }_{k-1}\left(G\right)$ 。

如果 $G^{\prime }$ 是图 $G$ 的一个子图并且 $k\ge 2$ ，那么 ${\phi }_k\left(G\right)\ge {\phi }_k\left(G^{\prime }\right)$ 。

证明：(1) 假设 $S$ 是 $G$ 的一个最小的 $k$ 路顶点覆盖集， $S^{\prime }$ 是 $G$ 的一个最小的 $k$ 路顶点覆盖集，显然我们有 $\left|S^{\prime }\right|\le \left|S\right|$ ，于是 ${\phi }_k\left(G\right)\le {\phi }_{k-1}\left(G\right)$ 。

(2) 假设 $S$ 是 $G$ 的一个 $k$ 路顶点覆盖集， $G^{\prime }$ 是图 $G$ 的一个子图，那么 $S\cap V\left(G\right)$ 是图 $G^{\prime }$ 的一个 $k$ 路顶点覆盖集，由于 $\left|S\cap V\left(G^{\prime }\right)\right|\le \left|S\right|$ ，于是 ${\phi }_k\left(G^{\prime }\right)\le {\phi }_k\left(G\right)$ 。

引理2.3：对于正整数 $k\ge 2$ ， $n\ge k$ ，我们有 ${\phi }_k\left(P_n^2\right)=2\lfloor \frac{n}{k+1}\rfloor$ 。

3. $P_m$ 和 $C_n$ 的笛卡尔乘积图的最小的k路顶点覆盖数的上界

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

定理3.1：如果 $k\ge 4$ ，并且 $\left(a,b\right)$ 为中间 $D_i$ 对，我们有如下的式子

${\phi }_k\left(P_m\square C_n\right)\le \min \left\{m\lceil \frac{n}{a+1}\rceil +n\lfloor \frac{m}{b+1}\rfloor -2\lceil \frac{n}{a+1}\rceil \lfloor \frac{m}{b+1}\rfloor ,m\lceil \frac{n}{b+1}\rceil +n\lfloor \frac{m}{a+1}\rfloor -2\lceil \frac{n}{b+1}\rceil \lfloor \frac{m}{a+1}\rfloor \right\}$

证明：首先我们构造一个最多有 $m\lceil \frac{n}{a+1}\rceil +n\lfloor \frac{m}{b+1}\rfloor -2\lceil \frac{n}{a+1}\rceil \lfloor \frac{m}{b+1}\rfloor$ 顶点的 $k$ 路顶点覆盖集去证明不等式的上界。让

$S_1=\left\{\left(u_i,v_j\right)\in P_m\square C_n|i\in [1,m],j\equiv 0\left(\mathrm{mod}\left(a+1\right)\right)\right\}\cup \left\{\left(u_i,v_n\right)\in P_m\square C_n|对于固定系数n\right\}$

并且

$S_2=\left\{\left(u_i,v_j\right)\in P_m\square C_n|j\in [1,m],i\equiv 0\left(\mathrm{mod}\left(b+1\right)\right)\right\}$ .

由于 $P_m\square C_n$ 中未被覆盖的最大连通子图同构于 $P_a\square P_b$ ，于是我们可以很容易得出 $S=\left(S_1\cup S_2\right)\backslash \left(S_1\cap S_2\right)$ 是一个 $k$ 路顶点覆盖集。

在 ${}^{u_i}C{}_n$ 中我们覆盖了每一个第 $a+1$ 个顶点和第 $n$ 个顶点，由于有 $m$ 层，所以 $\left|S_1\right|=m\lceil \frac{n}{a+1}\rceil$ 。同理，我们有 $\left|S_2\right|=n\lfloor \frac{m}{b+1}\rfloor$ ，由于我们把每个交叉的位置处的顶点算了两次，而且 $\left|S_1\cap S_2\right|=\lceil \frac{n}{a+1}\rceil \lfloor \frac{m}{b+1}\rfloor$ ，所以覆盖集 $S$ 的大小为

$\left|S\right|=m\lceil \frac{n}{a+1}\rceil +n\lfloor \frac{m}{b+1}\rfloor -2\lceil \frac{n}{a+1}\rceil \lfloor \frac{m}{b+1}\rfloor$ .

同样的，我们也可以通过交换 $a$ 和 $b$ 的位置去构造一个有 $m\lceil \frac{n}{b+1}\rceil +n\lfloor \frac{m}{a+1}\rfloor -2\lceil \frac{n}{b+1}\rceil \lfloor \frac{m}{a+1}\rfloor$ 个顶点的 $k$ 路顶点覆盖集。这样我们就得到了 ${\phi }_k\left(P_m\square C_n\right)$ 的上界。

4. $C_m$ 和 $P_n^2$ 的笛卡尔乘积图的最小的k路顶点覆盖数的下界

定理4.1：对于正整数 $k\ge 2,n\ge 4$ ，我们有如下结论：

${\phi }_k\left(C_m\square P_n^2\right)\ge \{\begin{array}{l}4\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{k+1}\rfloor +\lceil \frac{\left(m-1\right)\left(n-\lfloor \frac{n}{k+1}\rfloor \right)}{k}\rceil +2\lfloor \frac{n}{k+1}\rfloor ,如果m为奇数\\ 4\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{k+1}\rfloor +\lceil \frac{\left(m-1\right)\left(n-\lfloor \frac{n}{k+1}\rfloor \right)}{k}\rceil ,如果m为偶数\end{array}$

证明：首先在解决不等式下界的时候，我们先给出 ${\phi }_k\left(P_2\square P_{k+1}^2\right)$ 的精确值。很容易可以得出 ${\phi }_2\left(P_2\square P_3^2\right)=5$ ，但是在本定理中我们考虑 $k\ge 3$ 。

如果正整数 $k\ge 3$ ，我们有 ${\phi }_k\left(P_2\square P_{k+1}^2\right)=4$ 。我们构造一个有4个顶点 $k$ 路顶点覆盖集 $S$ ，去证明 ${\phi }_k\left(P_2\square P_{k+1}^2\right)\le 4$ 。让 $S=\left\{\left(u_1,v_t\right),\left(u_1,v_{t+1}\right),\left(u_2,v_t\right),\left(u_2,v_{t+1}\right)\right\}$ ，其中 $t=\lceil \frac{k}{2}\rceil$ 。如果我们删去 $S$ 中的点 $\left(u_i,v_j\right)$ 并且删去它的关联边，于是我们得到了 $P_2\square P_{k+1}^2$ 中最大的未被覆盖的子图 $P_2\square P_{\lfloor \frac{k}{2}\rfloor }^2$ 并且 $V\left(P_2\square P_{\lfloor \frac{k}{2}\rfloor }^2\right)=2\lfloor \frac{k}{2}\rfloor \le k-1$ 。于是 $S$ 是 $P_2\square P_{k+1}^2$ 的 $k$ 路顶点覆盖集，因此 ${\phi }_k\left(P_2\square P_{k+1}^2\right)\le 4$ 。

很显然 $C_{2k+2}\subseteq P_2\square P_{k+1}^2$ ，由引理我们得到 ${\phi }_k\left(P_2\square P_{k+1}^2\right)\le {\phi }_k\left(C_{2k+2}\right)=3$ 。通过 $P_2\square P_{k+1}^2$ 的结构我们知道，我们至少需要一个顶点去覆盖每一个 $P_2$ 层中的 $k+1$ 路，无论这两层的顶点是否相连我们都定义它们为 $\left(u_i,v_j\right),\left(u_p,v_q\right)$ ，我们可以知道 $C_{2k}\subseteq P_2\square P_{k+1}^2\backslash \left\{\left(u_i,v_j\right),\left(u_p,v_q\right)\right\}$ ，因此 ${\phi }_k\left(P_2\square P_{k+1}^2\right)\ge 2+{\phi }_k\left(C_{2k}\right)=4$ 。这样我们的等式 ${\phi }_k\left(P_2\square P_{k+1}^2\right)=4$ 得到了证明。

下面我们基于上述面我们证明过的等式给出 ${\phi }_k\left(C_m\square P_n^2\right)$ 的下界，我们可以把 $C_m\square P_n^2$ 分解成 $\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{k+1}\rfloor$ 个同构于 $P_2\square P_{k+1}^2$ 的不交子图，一个圈 $C_y$ (如图1所示)，其中 $y=\left(m-1\right)\left(n-\lfloor \frac{n}{k+1}\rfloor \right)$ 和一个对于奇数来说的 $P_n^2$ 。我们需要至少 ${\phi }_k\left(P_2\square P_{k+1}^2\right)$ 个顶点去覆盖每一个同构于 $P_2\square P_{k+1}^2$ 的子图，需要至少 ${\phi }_k\left(C_Y\right)$ 和 ${\phi }_k\left(P_n^2\right)$ 个顶点去分别覆盖子图 $C_y$ 和 $P_n^2$ 。因此对于奇数 $m$ 言，

${\phi }_k\left(C_m\square P_n^2\right)\ge 4\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{k+1}\rfloor +\lceil \frac{\left(m-1\right)\left(n-\lfloor \frac{n}{k+1}\rfloor \right)}{k}\rceil +2\lfloor \frac{n}{k+1}\rfloor$ .

对于偶数 $m$ 而言，我们把 $C_m\square P_n^2$ 分解成 $x$ 个同构于 $P_2\square P_{k+1}^2$ 的不交子图和一个次序为 $y$ 的圈 $C_y$ ，其中 $x=\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{k+1}\rfloor$ ， $y=\left(m-1\right)\left(n-\lfloor \frac{n}{k+1}\rfloor \right)$ 。我们需要至少 ${\phi }_k\left(P_2\square P_{k+1}^2\right)$ 个顶点去覆盖每一个同构于 $P_2\square P_{k+1}^2$ 的子图，需要至少 ${\phi }_k\left(C_Y\right)$ 个顶点去覆盖子图 $C_y$ 。因此有

Figure 1. A partition of $C_m\square P_n^2$ for odd m

图1. 当m为奇数时， $C_m\square P_n^2$ 的一个分解

${\phi }_k\left(C_m\square P_n^2\right)\ge 4\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{k+1}\rfloor +\lceil \frac{\left(m-1\right)\left(n-\lfloor \frac{n}{k+1}\rfloor \right)}{k}\rceil$ .

${\phi }_k\left(C_m\square P_n^2\right)\ge 4\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{k+1}\rfloor +\lceil \frac{\left(mn-\left(m-1\right)\lfloor \frac{n}{k+1}\rfloor \right)}{k}\rceil$ .

证明：根据定理4.1的证明过程，我们可以把 $C_m\square P_n^2$ 分解成 $x$ 个同构于 $P_2\square P_{k+1}^2$ 的不交子图和一个次序为 $y$ 的圈 $C_y$ ，其中 $x=\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{k+1}\rfloor$ ， $y=mn-\left(m-1\right)\lfloor \frac{n}{k+1}\rfloor$ 。我们需要至少 ${\phi }_k\left(P_2\square P_{k+1}^2\right)$ 个顶点去覆盖每一个同构于 $P_2\square P_{k+1}^2$ 的子图，需要至少 ${\varphi }_k\left(C_Y\right)$ 个顶点去覆盖子图 $C_y$ 。因此有

$\begin{array}{c}{\phi }_k\left(C_m\square P_n^2\right)\ge x{\phi }_k\left(P_2\square P_{k+1}^2\right)+y{\phi }_k\left(C_y\right)=4x+\lfloor \frac{y}{k}\rfloor \\ =4\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{k+1}\rfloor +\lceil \frac{\left(mn-\left(m-1\right)\lfloor \frac{n}{k+1}\rfloor \right)}{k}\rceil .\end{array}$