路和圈的笛卡尔积的全隔离数

doi:10.12677/aam.2025.149398

期刊菜单

路和圈的笛卡尔积的全隔离数
Total Isolation Number of the Cartesian Product of Paths and Cycles

DOI: 10.12677/aam.2025.149398, PDF, HTML, XML, 国家自然科学基金支持
作者: 赵宇慧：青海师范大学数学与统计学院，青海西宁；李贺：山西传媒学院信息工程学院，山西晋中；张淑敏^*：青海师范大学数学与统计学院，青海西宁；藏语智能信息处理及应用国家重点实验室，青海西宁
关键词: 部分控制；全隔离数；笛卡尔积；Partial Domination； Total Isolation Number； Cartesian Product

摘要: 设

G = (V, E)

是一个图且集合

S \subseteq V

，如果V\N[S]是G的一个独立集，则集合S称作是G的一个隔离集。当S是一个隔离集且G[S]不含孤立点时，集合S称作是G的一个全隔离集。图的全隔离数是图中最小的全隔离集的基数。本文主要研究路和圈的笛卡尔积的全隔离数。

Abstract: Let

G = (V, E)

be a graph and

S \subseteq V

. The set S is called an isolating set of G if V\N[S] is an independent set of G. When S is an isolating set and G[S] contains no isolated vertices, S is a total isolating set of G. The total isolation number of a graph is the minimum cardinality of a total isolating set in the graph. This paper mainly studies the total isolation number of the Cartesian product of paths and cycles.

文章引用：赵宇慧, 李贺, 张淑敏. 路和圈的笛卡尔积的全隔离数[J]. 应用数学进展, 2025, 14(9): 46-59. https://doi.org/10.12677/aam.2025.149398

1. 引言

随着计算机科学和网络通讯技术的飞速发展，图的控制理论成为图论研究中一个发展迅速且重要的领域，截至目前已经取得了许多研究成果。图的部分控制是对经典控制理论的一个推广与延伸，随着图部分控制理论的不断深入研究，衍生出了许多新的部分控制参数，例如独立隔离、全隔离等，这些新的参数为解决图的部分控制问题提供了更丰富、更灵活的手段，推动了部分控制领域的进一步发展。学界已对隔离数展开了广泛且深入的研究(参见文献[1 ]-[12])。图的隔离数和点–边控制数是同一个概念，同理图的全隔离数和全顶点–边控制数也是同一个概念。其中，全顶点–边控制数最初由Boutrig和Chellali 提出。2018年，Boutrig和Chellali 证明了二分图的全隔离数是NP完全问题。接着表明：若T是

一棵不同构于星的树，其阶数为n，有l片叶子和s个支撑顶点，则 $γ_{v e}^{t} (T) \leq \frac{n - l + s}{2}$ 。此外，他们刻画了达到该上界的所有树，并建立了满足 $γ_{v e}^{t} (G) = 2 γ_{v e} (G)$ 的图G的必要条件，并对所有满足 $γ_{v e}^{t} (T) = 2 γ_{v e} (T)$ 的树T进行了完整刻画。2021年，Ahangar和Chellali [14]等人刻画了所有满足 $γ_{v e}^{t} (T) = γ_{t} (T)$ 或者 $γ_{v e}^{t} (T) = γ_{v e} (T)$ 的树。同年，Senthilkumar和Venkatakrishnan [15]等人证明了若T是一棵非平凡树，其阶数为n，有l片叶子和s个支撑顶点，则 $γ_{v e}^{t} (T) \geq \frac{n - l + s + 6}{4}$ 并刻画了达到界的树。2022年，Singhwal和Reddy [16]证明了与问题 $γ_{v e}^{t} (G)$ 对应的判定问题在弦图、星凸二分图、梳凸二分图以及平面图中均为NP

完全问题。2024年，Boyer和Goddard [17]证明了大多数图都能划分为两个不相交的全隔离集，并刻画了其中的例外情况。本文给出了路和圈的笛卡尔积的全隔离数的上下界并证明了部分界是紧的。

2. 基本概念

在本文中，我们所考虑的所有图都是有限、简单且无向的。对于未提及的概念，我们参考[18]。设 $G = (V, E)$ 是一个简单无向图，其顶点集V的阶为n，边集E的大小为m，即 $n = | V (G) |$ 且 $e = | E (G) |$ 。顶点v的度为 $d_{G} (v) = | N_{G} (v) |$ 。孤立点是指度为0的点。图G中顶点v的邻点是指与v相邻的顶点u。图G中顶点v的开邻域 $N_{G} (v)$ 是v的所有邻点构成的集合，其中 $N_{G} (v) = {u \in V (G) | u v \in E (G)}$ 。v的闭邻域为 $N_{G} [v] = N_{G} (v) \cup {v}$ 。集合 $S \subseteq V (G)$ 的邻域是集合 $N_{G} (S) = \cup_{v \in S} N_{G} (v)$ 。集合 $S \subseteq V (G)$ 的闭邻域是集合 $N_{G} [S] = N_{G} (S) \cup S$ 。设G[S]表示S在图G中的导出子图。 $G - S$ 表示图G删掉顶点集S后得到的图。图 $P_{n}$ 和 $C_{n}$ 分别表示n个顶点的路和圈。 $G \to H$ 的同态是一个映射 $f : V (G) \to V (H)$ ，使得当 $u v \in E (G)$ 时， $f (u) f (v) \in E (H)$ 。

定义1. 如果一个集合 $S \subseteq V$ ，对于每一个不属于S的顶点都可以在S中找到至少一个邻点，则称S为图G的控制集，图G中最小控制集的基数称为图G的控制数，记为 $γ (G)$ 。

定义2. 如果一个集合 $S \subseteq V$ 满足 $N_{G} (S) = V (G)$ ，则称S为图G的全控制集，图G中最小全控制集的基数称为图G的全控制数，记为 $γ_{t} (G)$ 。

定义3. [1] 如果一个集合 $S \subseteq V$ 满足 $V (G) \ N_{G} [S]$ 是图G的一个独立集(集合中没有在图G中相邻的顶点)，则称S为图G的隔离集，图G中最小隔离集的基数称为图G的隔离数，记为 $ι (G)$ 。

定义4. [6] 如果一个集合 $S \subseteq V$ 是一个隔离集且S的导出子图没有孤立点，则称S为图G的全隔离集，图G中最小全隔离集的基数称为图G的全隔离数，记为 $ι_{t} (G)$ 。图G的最小全隔离集简记为 $ι_{t} (G)$ -集。

定义5. 两个图G和H的笛卡尔积是图 $G □ H$ ，其顶点集为 $V (G □ H) = V (G) \times V (H)$ ，且 $(u, v) (x, y) \in E (G □ H)$ 当且仅当(i) $u = v$ 且 $x y \in E (H)$ ，或者(ii) $u v \in E (G)$ 且 $x = y$ 。根据定义，可得出 $G □ H ≅ H □ G$ 。

3. 路和路的笛卡尔积的全隔离数

这一节给出路和路的笛卡尔积的全隔离数的上界。首先给出所需引理。

引理3.1. 当 $n \geq 3$ 时， $P_{3} □ P_{n}$ 的全隔离数

$ι_{t} (P_{3} □ P_{n}) = {\begin{array}{l} 2 ⌊ \frac{n}{3} ⌋ + 1 & n \equiv 2 (\mod 3), \\ 2 ⌊ \frac{n}{3} ⌋ & otherwise . \end{array}$

证明. 先证明 $ι_{t} (P_{3} □ P_{n}) \leq {\begin{array}{l} 2 ⌊ \frac{n}{3} ⌋ + 1 & n \equiv 2 (\mod 3) \\ 2 ⌊ \frac{n}{3} ⌋ & otherwise \end{array}$ 。对n进行归纳，当对n进行归纳，当 $n = 3$ ，有 $ι_{t} (P_{3} □ P_{3}) = 2 = 2 \times ⌊ \frac{3}{3} ⌋$ 。当 $n = 4$ ，有 $ι_{t} (P_{3} □ P_{4}) = 2 = 2 \times ⌊ \frac{4}{3} ⌋$ 。当 $n = 5$ ，有 $ι_{t} (P_{3} □ P_{5}) = 3 = 2 \times ⌊ \frac{5}{3} ⌋ + 1$ 。设结论对大于等于3小于n的自然数成立。以下证对 $n \geq 6$ 成立。显然， $ι_{t} (P_{3} □ P_{n}) \leq ι_{t} (P_{3} □ P_{3}) + ι_{t} (P_{3} □ P_{n - 3})$ 。根据归纳假设，当 $n - 3 \geq 3$ 时，

$ι_{t} (P_{3} □ P_{n - 3}) \leq {\begin{array}{l} 2 ⌊ \frac{n - 3}{3} ⌋ + 1 & n \equiv 2 (\mod 3), \\ 2 ⌊ \frac{n - 3}{3} ⌋ & otherwise . \end{array}$

所以，

$ι_{t} (P_{3} □ P_{n}) \leq {\begin{array}{l} 2 ⌊ \frac{n}{3} ⌋ + 1 & n \equiv 2 (\mod 3), \\ 2 ⌊ \frac{n}{3} ⌋ & otherwise . \end{array}$

设D是 $P_{3} □ P_{n}$ 的一个全隔离集且 $| D | < {\begin{array}{l} 2 ⌊ \frac{n - 3}{3} ⌋ + 1 & n \equiv 2 (\mod 3) \\ 2 ⌊ \frac{n - 3}{3} ⌋ & otherwise \end{array}$ ，则在 $P_{3} □ P_{n}$ 中至少存在某个区域含D中两个或三个顶点且同构于 $P_{3} □ P_{5}$ (所含D中的三个顶点并不能构成 $P_{3} □ P_{5}$ 的全隔离集)，图 $P_{3} □ P_{n} - N [D]$ 至少在这个区域中含一条边。这与全隔离集定义矛盾，所以结论成立。

由此， $ι_{t} (P_{3} □ P_{n}) = {\begin{array}{l} 2 ⌊ \frac{n}{3} ⌋ + 1 & n \equiv 2 (\mod 3) \\ 2 ⌊ \frac{n}{3} ⌋ & otherwise \end{array}$ 。

例1. 在图1中，我们展示 $P_{3} □ P_{3}$ 至 $P_{3} □ P_{7}$ 等5个图全隔离集的分布，红色点为控制点，黑色点为被控制顶点，绿色为孤立顶点。可以从图中看出，每3个为一个循环增加2个控制点。

Figure 1. A $ι_{t} (P_{3} □ P_{n})$ -set of $P_{3} □ P_{n}$ ( $3 \leq n \leq 7$ )

图1. $P_{3} □ P_{n} (3 \leq n \leq 7)$ 最小的全隔离集

Figure 2. A total isolating set of $P_{9} □ P_{9}$

图2. $P_{9} □ P_{9}$ 的一个全隔离集

定理3.1. [19] 当整数 $n \geq 2$ 时， $γ_{t} (P_{n}) = ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{4} ⌉ - ⌊ \frac{n}{4} ⌋$ 。当 $n \geq 3$ 时， $γ_{t} (P_{n}) = γ_{t} (C_{n})$ 。

证明构造的集合在给定情况下满足全隔离集的两个定义条件以及计算构造集合基数的过程在定理

3.2当 $n \equiv 0 (\mod 3)$ 且 $m \equiv 0 (\mod 3)$ 时给出了详细推导，后面其他情况证明过程与之类似，我们将不再赘述。由于 $P_{n} □ P_{m} ≅ P_{m} □ P_{n}$ ，所以 $P_{n} □ P_{m}$ 的全隔离数只需考虑以下六种情况。

定理3.2. 对于正整数 $n, m \geq 3$ ， $P_{n} □ P_{m}$ 的全隔离数

$2 ⌊ \frac{n}{3} ⌋ \leq ι_{t} (P_{n} □ P_{m}) \leq {\begin{array}{l} \frac{2 m n}{9} & n \equiv 0 (\mod 3), m \equiv 0 (\mod 3); \\ \frac{2 (m - 1) n}{9} + 2 ⌊ \frac{n}{6} ⌋ & n \equiv 0 (\mod 3), m \equiv 1 (\mod 3); \\ \frac{(2 m - 1) n}{9} + ⌊ \frac{n}{6} ⌋ & n \equiv 0 (\mod 3), m \equiv 2 (\mod 3); \\ \frac{2 m n - 2 n - 2 m + 2}{9} + 2 ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ & n \equiv 1 (\mod 3), m \equiv 1 (\mod 3); \\ \frac{2 m n - 2 m - n + 1}{9} + ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ & n \equiv 1 (\mod 3), m \equiv 2 (\mod 3); \\ \frac{2 m n + 2 m - n - 1}{9} + ⌊ \frac{n + 1}{6} ⌋ & n \equiv 2 (\mod 3), m \equiv 2 (\mod 3) . \end{array}$

该下界是紧的。除了 $n \equiv 1$ 或 $2 (\mod 3)$ 且 $m \equiv 2 (\mod 3)$ 的情况，所给上界是紧的。

证明. 设 $G = P_{n} □ P_{m}$ 并且 $V (G) = {(i, j) | 1 \leq i \leq n, 1 \leq j \leq m}$ 。进一步设 $A_{i} = {(i, j) | 1 \leq j \leq m}$ 并且 $B_{j} = {(i, j) | 1 \leq i \leq n}$ ，则 $G [A_{i}] ≅ P_{m}$ 且 $G [B_{j}] ≅ P_{n}$ 。显然，根据引理3.1以及 $n, m \geq 3$ ， $ι_{t} (P_{n} □ P_{m}) \geq ι_{t} (P_{n} □ P_{3}) \geq 2 ⌊ \frac{n}{3} ⌋$ 。当 $n = m = 3$ 时， $ι_{t} (P_{3} □ P_{3}) = 2 = 2 ⌊ \frac{3}{3} ⌋$ 。因此，下界是紧的。

当 $n \equiv 0 (\mod 3)$ 且 $m \equiv 0 (\mod 3)$ 时，设 $S_{1} = {(i, j) | i \equiv 2 (\mod 6), j \equiv 0 (\mod 3)}$ ， $S_{2} = {(i, j) | i \equiv 5 (\mod 6), j \equiv 1 (\mod 3)}$ ， $S_{3} = {(i, j) | i, j \equiv 2 (\mod 3)}$ 。如图2，对于 $P_{9} □ P_{9}$ 来说， $S_{1}$ 对应图中红色的顶点， $S_{2}$ 对应图中黄色的顶点， $S_{3}$ 对应图中黑色的顶点，绿色代表未被图中红色、黑色、黄色顶点控制的顶点。则 $S = S_{1} \cup S_{2} \cup S_{3}$ 是图G的一个全隔离集。如图2，对于 $P_{9} □ P_{9}$ 来说，红色框内黑色和红色顶点恰好是一个 $ι_{t} (P_{3} □ P_{9})$ -集，绿色框内黑色和黄色顶点恰好是一个 $ι_{t} (P_{3} □ P_{10})$ -集。观察S可以得到，在 $P_{n} □ P_{m}$ 中 $ι_{t} (P_{3} □ P_{m})$ -集有 $⌈ \frac{n}{6} ⌉$ 个且 $ι_{t} (P_{3} □ P_{m + 1})$ -集有 $⌊ \frac{n}{6} ⌋$ 个。因此，根据引理3.1得

$ι_{t} (G) \leq | S | \leq ι_{t} (P_{3} □ P_{m}) ⌈ \frac{n}{6} ⌉ + ι_{t} (P_{3} □ P_{m + 1}) ⌊ \frac{n}{6} ⌋ = 2 ⌊ \frac{m}{3} ⌋ ⌈ \frac{n}{6} ⌉ + 2 ⌊ \frac{m + 1}{3} ⌋ ⌊ \frac{n}{6} ⌋ = \frac{2 m n}{9} .$

当 $n = m = 3$ 时， $ι_{t} (P_{3} □ P_{3}) = 2 = \frac{2 \times 3 \times 3}{9}$ 。

当 $n \equiv 0 (\mod 3)$ 且 $m \equiv 1 (\mod 3)$ 时，设 $S_{4} = {(i, j) | i \equiv 5 (\mod 6), j = m - 1}$ 。则 $S^{'} = S_{1} \cup S_{2} \cup S_{3} \cup S_{4}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | S^{'} | \leq ι_{t} (P_{3} □ P_{m}) ⌈ \frac{n}{6} ⌉ + (ι_{t} (P_{3} □ P_{m + 1}) + 1) ⌊ \frac{n}{6} ⌋ \\ = 2 ⌊ \frac{m}{3} ⌋ ⌈ \frac{n}{6} ⌉ + (2 ⌊ \frac{m + 1}{3} ⌋ + 1 + 1) ⌊ \frac{n}{6} ⌋ \\ = \frac{2 (m - 1) n}{9} + 2 ⌊ \frac{n}{6} ⌋ . \end{matrix}$

当 $n = 3$ ， $m = 4$ 时， $ι_{t} (P_{3} □ P_{4}) = 2 = \frac{2 \times (4 - 1) \times 3}{9} + 2 ⌊ \frac{3}{6} ⌋$ 。

当 $n \equiv 0 (\mod 3)$ 且 $m \equiv 2 (\mod 3)$ 时，设 $S_{5} = {(i, j) | i \equiv 2 (\mod 6), j = m - 1}$ ， $S_{6} = {(i, j) | i \equiv 2 (\mod 6), j = m}$ 。则 $S^{″} = (S \ S_{6}) \cup S_{5}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | S^{″} | \leq ι_{t} (P_{3} □ P_{m}) ⌈ \frac{n}{6} ⌉ + ι_{t} (P_{3} □ P_{m + 1}) ⌊ \frac{n}{6} ⌋ \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) ⌈ \frac{n}{6} ⌉ + 2 ⌊ \frac{m + 1}{3} ⌋ ⌊ \frac{n}{6} ⌋ \\ = \frac{(2 m - 1) n}{9} + ⌊ \frac{n}{6} ⌋ . \end{matrix}$

当 $n = 3$ ， $m = 5$ 时， $ι_{t} (P_{3} □ P_{5}) = 3 = \frac{(2 \times 5 - 1) \times 3}{9} + ⌊ \frac{3}{6} ⌋$ 。

当 $n \equiv 1 (\mod 3)$ 且 $m \equiv 1 (\mod 3)$ ， $S_{7} = {(i, j) | i = n, j \equiv 2 或 3 (\mod 4)} \cup {(n, m - 1)}$ 。则 $D = S \cup S_{7} \cup S_{4}$ 是图G的一个全隔离集。因此，根据引理3.1和定理3.1得

$\begin{matrix} ι_{t} (G) \leq | D | \leq ι_{t} (P_{3} □ P_{m}) ⌈ \frac{n - 1}{6} ⌉ + (ι_{t} (P_{3} □ P_{m + 1}) + 1) ⌊ \frac{n - 1}{6} ⌋ + γ_{t} (P_{m}) \\ = 2 ⌊ \frac{m}{3} ⌋ ⌈ \frac{n - 1}{6} ⌉ + (2 ⌊ \frac{m + 1}{3} ⌋ + 1 + 1) ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ \\ = \frac{2 m n - 2 n - 2 m + 2}{9} + 2 ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ . \end{matrix}$

当 $n = 4$ ， $m = 4$ 时， $ι_{t} (P_{4} □ P_{4}) = 4 = \frac{2 \times 4 \times 4 - 2 \times 4 - 2 \times 4 + 2}{9} + 2 ⌊ \frac{4 - 1}{6} ⌋ + ⌊ \frac{4}{2} ⌋ + ⌈ \frac{4}{4} ⌉ - ⌊ \frac{4}{4} ⌋$ 。

当 $n \equiv 1 (\mod 3)$ 且 $m \equiv 2 (\mod 3)$ 时，则 $D^{'} = (S \ S_{6}) \cup S_{5} \cup S_{7}$ ，是图G的一个全隔离集。因此，根据引理3.1和定理3.1得

$\begin{matrix} ι_{t} (G) \leq | D^{'} | \leq ι_{t} (P_{3} □ P_{m}) ⌈ \frac{n - 1}{6} ⌉ + ι_{t} (P_{3} □ P_{m + 1}) ⌊ \frac{n - 1}{6} ⌋ + γ_{t} (P_{m}) \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) ⌈ \frac{n - 1}{6} ⌉ + 2 ⌊ \frac{m + 1}{3} ⌋ ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ \\ = \frac{2 m n - 2 m - n + 1}{9} + ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ . \end{matrix}$

当 $n \equiv 2 (\mod 3)$ 且 $m \equiv 2 (\mod 3)$ 时， $S^{″}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | S^{″} | \leq ι_{t} (P_{3} □ P_{m}) ⌈ \frac{n + 1}{6} ⌉ + ι_{t} (P_{3} □ P_{m + 1}) ⌊ \frac{n + 1}{6} ⌋ \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) ⌈ \frac{n + 1}{6} ⌉ + 2 ⌊ \frac{m + 1}{3} ⌋ ⌊ \frac{n + 1}{6} ⌋ \\ = \frac{2 m n + 2 m - n - 1}{9} + ⌊ \frac{n + 1}{6} ⌋ . \end{matrix}$

4. 路和圈的笛卡尔积的全隔离数

这一节给出路和圈的笛卡尔积的全隔离数的上界。

定理4.1. 对于正整数 $n, m \geq 3$ ，当 $n \equiv 0 (\mod 3)$ 时， $C_{n} □ P_{m}$ 的全隔离数

$\frac{2 n}{3} \leq ι_{t} (C_{n} □ P_{m}) \leq {\begin{array}{l} \frac{2 m n}{9} & n \equiv 0 (\mod 6), m \equiv 0 (\mod 3); \\ \frac{2 m n + n}{9} & n \equiv 0 (\mod 6), m \equiv 1 (\mod 3); \\ \frac{4 m n + n}{18} & n \equiv 0 (\mod 6), m \equiv 2 (\mod 3); \\ \frac{2 m n + 3 m}{9} & n \equiv 3 (\mod 6), m \equiv 0 (\mod 3); \\ \frac{2 m n + 3 m + n - 3}{9} & n \equiv 3 (\mod 6), m \equiv 1 (\mod 3); \\ \frac{4 m n + 6 m + n - 3}{18} & n \equiv 3 (\mod 6), m \equiv 2 (\mod 3) . \end{array}$

该下界是紧的。当 $n \equiv 0 (\mod 6)$ 且 $m \equiv 0 (\mod 3)$ 或者 $n \equiv 3 (\mod 6)$ 且 $m \equiv 1 (\mod 3)$ 时，上界是紧的。

证明. 设 $G = C_{n} □ P_{m}$ 并且 $V (G) = {(i, j) | 1 \leq i \leq n, 1 \leq j \leq m}$ 。进一步设 $A_{i} = {(i, j) | 1 \leq j \leq m}$ 并且 $B_{j} = {(i, j) | 1 \leq i \leq n}$ ，则 $G [A_{i}] ≅ P_{m}$ 且 $G [B_{j}] ≅ C_{n}$ 。显然，根据引理3.1， $n \equiv 0 (\mod 3)$ 以及 $n, m \geq 3$ ， $ι_{t} (C_{n} □ P_{m}) \geq ι_{t} (P_{n} □ P_{3}) = \frac{2 n}{3}$ 。当 $n = m = 3$ 时， $ι_{t} (C_{3} □ P_{3}) = 2 = \frac{2 \times 3}{3}$ 。因此，下界是紧的。

当 $n \equiv 0 (\mod 6)$ 且 $m \equiv 0 (\mod 3)$ 时，设 $S_{1} = {(i, j) | i \equiv 2 (\mod 6), j \equiv 0 (\mod 3)}$ ， $S_{2} = {(i, j) | i \equiv 5 (\mod 6), j \equiv 1 (\mod 3)}$ ， $S_{3} = {(i, j) | i, j \equiv 2 (\mod 3)}$ 。则 $S = S_{1} \cup S_{2} \cup S_{3}$ 是图G的一个全隔离集。因此，根据引理3.1得

$ι_{t} (G) \leq | S | \leq ι_{t} (P_{3} □ P_{m}) \frac{n}{6} + ι_{t} (P_{3} □ P_{m + 1}) \frac{n}{6} = 2 ⌊ \frac{m}{3} ⌋ \frac{n}{6} + 2 ⌊ \frac{m + 1}{3} ⌋ \frac{n}{6} = \frac{2 m n}{9} .$

当 $n = 6$ ， $m = 3$ 时， $ι_{t} (C_{6} □ P_{3}) = 4 = \frac{2 \times 6 \times 3}{9}$ 。

当 $n \equiv 0 (\mod 6)$ 且 $m \equiv 1 (\mod 3)$ 时，设 $S_{4} = {(i, j) | i \equiv 5 (\mod 6), j = m - 1}$ 。则 $S^{'} = S_{1} \cup S_{2} \cup S_{3} \cup S_{4}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | S^{'} | \leq ι_{t} (P_{3} □ P_{m}) \frac{n}{6} + (ι_{t} (P_{3} □ P_{m + 1}) + 1) \frac{n}{6} \\ = 2 ⌊ \frac{m}{3} ⌋ \frac{n}{6} + (2 ⌊ \frac{m + 1}{3} ⌋ + 1 + 1) \frac{n}{6} \\ = \frac{2 m n + n}{9} . \end{matrix}$

当 $n \equiv 0 (\mod 6)$ 且 $m \equiv 2 (\mod 3)$ 时，设 $S_{5} = {(i, j) | i \equiv 2 (\mod 6), j = m - 1}$ ， $S_{6} = {(i, j) | i \equiv 2 (\mod 6), j = m}$ 。则 $S^{″} = (S \ S_{6}) \cup S_{5}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | S^{″} | \leq ι_{t} (P_{3} □ P_{m}) \frac{n}{6} + ι_{t} (P_{3} □ P_{m + 1}) \frac{n}{6} \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) \frac{n}{6} + 2 ⌊ \frac{m + 1}{3} ⌋ \frac{n}{6} \\ = \frac{4 m n + n}{18} . \end{matrix}$

当 $n \equiv 3 (\mod 6)$ 且 $m \equiv 0 (\mod 3)$ 时，设 $S_{7} = {(i, j) | i = n - 1, 1 \leq j \leq m}$ 。则 $D = S \cup S_{7}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | D | \leq ι_{t} (P_{3} □ P_{m}) \frac{n - 3}{6} + ι_{t} (P_{3} □ P_{m + 1}) \frac{n - 3}{6} + m \\ = 2 ⌊ \frac{m}{3} ⌋ \frac{n - 3}{6} + 2 ⌊ \frac{m + 1}{3} ⌋ \frac{n - 3}{6} + m \\ = \frac{2 m n + 3 m}{9} . \end{matrix}$

当 $n \equiv 3 (\mod 6)$ 且 $m \equiv 1 (\mod 3)$ 时，则 $D^{'} = S^{'} \cup S_{7}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | D^{'} | \leq ι_{t} (P_{3} □ P_{m}) \frac{n - 3}{6} + (ι_{t} (P_{3} □ P_{m + 1}) + 1) \frac{n - 3}{6} + m \\ = 2 ⌊ \frac{m}{3} ⌋ \frac{n - 3}{6} + (2 ⌊ \frac{m + 1}{3} ⌋ + 1 + 1) \frac{n - 3}{6} + m \\ = \frac{2 m n + 3 m + n - 3}{9} . \end{matrix}$

当 $n = 3$ ， $m = 4$ 时， $ι_{t} (C_{3} □ P_{4}) = 4 = \frac{2 \times 3 \times 4 + 3 \times 4 + 3 - 3}{9}$ 。

当 $n \equiv 3 (\mod 6)$ 且 $m \equiv 2 (\mod 3)$ 时， $D^{″} = S^{″} \cup S_{7}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | D^{″} | \leq ι_{t} (P_{3} □ P_{m}) \frac{n - 3}{6} + ι_{t} (P_{3} □ P_{m + 1}) \frac{n - 3}{6} + m \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) \frac{n - 3}{6} + 2 ⌊ \frac{m + 1}{3} ⌋ \frac{n - 3}{6} + m \\ = \frac{4 m n + 6 m + n - 3}{18} . \end{matrix}$

定理4.2. 对于正整数 $n, m \geq 3$ ，当 $n \equiv 1 (\mod 3)$ 时， $C_{n} □ P_{m}$ 的全隔离数

$\frac{2 n - 2}{3} \leq ι_{t} (C_{n} □ P_{m}) \leq {\begin{array}{l} \frac{2 m n - 2 m}{9} + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ & m \equiv 0 (\mod 3); \\ \frac{2 m n - 2 n - 2 m + 2}{9} + 2 ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ & m \equiv 1 (\mod 3); \\ \frac{2 m n - 2 m - n + 1}{9} + ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ & m \equiv 2 (\mod 3) . \end{array}$

当 $m \equiv 1 (\mod 3)$ 时，上界是紧的。

证明. 设 $G = C_{n} □ P_{m}$ 并且 $V (G) = {(i, j) | 1 \leq i \leq n, 1 \leq j \leq m}$ 。进一步设 $A_{i} = {(i, j) | 1 \leq j \leq m}$ 并且 $B_{j} = {(i, j) | 1 \leq i \leq n}$ ，则 $G [A_{i}] ≅ P_{m}$ 且 $G [B_{j}] ≅ C_{n}$ 。显然，根据引理3.1， $n \equiv 1 (\mod 3)$ 以及 $n, m \geq 3$ ， $ι_{t} (C_{n} □ P_{m}) \geq ι_{t} (P_{n} □ P_{3}) = \frac{2 n - 2}{3}$ 。

当 $n \equiv 1 (\mod 3)$ 且 $m \equiv 0 (\mod 3)$ 时，设 $S_{1} = {(i, j) | i \equiv 2 (\mod 6), j \equiv 0 (\mod 3)}$ ， $S_{2} = {(i, j) | i \equiv 5 (\mod 6), j \equiv 1 (\mod 3)}$ ， $S_{3} = {(i, j) | i, j \equiv 2 (\mod 3)}$ ， $S_{4} = {(i, j) | i = n, j \equiv 2 或 3 (\mod 4)} \cup {(n, m - 1)}$ 。则 $S = S_{1} \cup S_{2} \cup S_{3} \cup S_{4}$ 是图G的一个全隔离集。因此，根据引理3.1和定理3.1得

$\begin{matrix} ι_{t} (G) \leq | S | \leq ι_{t} (P_{3} □ P_{m}) ⌊ \frac{n - 1}{6} ⌋ + ι_{t} (P_{3} □ P_{m + 1}) ⌊ \frac{n - 1}{6} ⌋ + γ_{t} (P_{m}) \\ = 2 ⌈ \frac{m}{3} ⌉ ⌊ \frac{n - 1}{6} ⌋ + 2 ⌊ \frac{m + 1}{3} ⌋ ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ \\ = \frac{2 m n - 2 m}{9} + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ . \end{matrix}$

在其余两种情形的证明过程中，所构造的全隔离集可参照定理3.2对应情形的思路与方法，最终能够推导出相应的上界。当 $n = 4$ ， $m = 4$ 时， $ι_{t} (C_{4} □ P_{4}) = 4 = \frac{2 \times 4 \times 4 - 2 \times 4 - 2 \times 4 + 2}{9} + 2 ⌊ \frac{4 - 1}{6} ⌋ + ⌊ \frac{4}{2} ⌋ + ⌈ \frac{4}{4} ⌉ - ⌊ \frac{4}{4} ⌋$ 。因此，当 $m \equiv 1 (\mod 3)$ 时，上界是紧的。

定理4.3. 对于正整数 $n, m \geq 3$ ，当 $n \equiv 2 (\mod 3)$ 时， $C_{n} □ P_{m}$ 的全隔离数

$\frac{2 n - 1}{3} \leq ι_{t} (C_{n} □ P_{m}) \leq {\begin{array}{l} \frac{2 m n + 2 m}{9} & m \equiv 0 (\mod 3); \\ \frac{2 m n - 2 n + 2 m - 2}{9} + 2 ⌊ \frac{n + 1}{6} ⌋ & m \equiv 1 (\mod 3); \\ \frac{2 m n + 2 m - n - 1}{9} + ⌊ \frac{n + 1}{6} ⌋ & m \equiv 2 (\mod 3) . \end{array}$

当 $m \equiv 0 (\mod 3)$ 时，上界是紧的。

证明. 设 $G = C_{n} □ P_{m}$ 并且 $V (G) = {(i, j) | 1 \leq i \leq n, 1 \leq j \leq m}$ 。进一步设 $A_{i} = {(i, j) | 1 \leq j \leq m}$ 并且 $B_{j} = {(i, j) | 1 \leq i \leq n}$ ，则 $G [A_{i}] ≅ P_{m}$ 且 $G [B_{j}] ≅ C_{n}$ 。显然，根据引理3.1， $n \equiv 2 (\mod 3)$ 以及 $n, m \geq 3$ ， $ι_{t} (C_{n} □ P_{m}) \geq ι_{t} (P_{n} □ P_{3}) = \frac{2 n - 1}{3}$ 。

当 $n \equiv 2 (\mod 3)$ 且 $m \equiv 0 (\mod 3)$ 时，设 $S_{1} = {(i, j) | i \equiv 2 (\mod 6), j \equiv 0 (\mod 3)}$ ， $S_{2} = {(i, j) | i \equiv 5 (\mod 6), j \equiv 1 (\mod 3)}$ ， $S_{3} = {(i, j) | i, j \equiv 2 (\mod 3)}$ 。则 $S = S_{1} \cup S_{2} \cup S_{3}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | S | \leq ι_{t} (P_{3} □ P_{m}) ⌈ \frac{n + 1}{6} ⌉ + ι_{t} (P_{3} □ P_{m + 1}) ⌊ \frac{n + 1}{6} ⌋ \\ = 2 ⌊ \frac{m}{3} ⌋ ⌈ \frac{n + 1}{6} ⌉ + 2 ⌊ \frac{m + 1}{3} ⌋ ⌊ \frac{n + 1}{6} ⌋ \\ = \frac{2 m n + 2 m}{9} . \end{matrix}$

当 $n = 5$ ， $m = 3$ 时， $ι_{t} (C_{5} □ P_{3}) = 4 = \frac{2 \times 5 \times 3 + 2 \times 3}{9}$ 。

当 $n \equiv 2 (\mod 3)$ 且 $m \equiv 1 (\mod 3)$ 时，设 $S_{4} = {(i, j) | i \equiv 5 (\mod 6), j = m - 1}$ 。则 $S^{'} = S_{1} \cup S_{2} \cup S_{3} \cup S_{4}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | S^{'} | \leq ι_{t} (P_{3} □ P_{m}) ⌈ \frac{n + 1}{6} ⌉ + (ι_{t} (P_{3} □ P_{m + 1}) + 1) ⌊ \frac{n + 1}{6} ⌋ \\ = 2 ⌊ \frac{m}{3} ⌋ ⌈ \frac{n + 1}{6} ⌉ + (2 ⌊ \frac{m + 1}{3} ⌋ + 1 + 1) ⌊ \frac{n + 1}{6} ⌋ \\ = \frac{2 m n - 2 n + 2 m - 2}{9} + 2 ⌊ \frac{n + 1}{6} ⌋ . \end{matrix}$

当 $n \equiv 2 (\mod 3)$ 且 $m \equiv 2 (\mod 3)$ 时，所构造的全隔离集可参照定理3.2对应情形的思路与方法，最终能够推导出相应的上界。

5. 圈和圈的笛卡尔积的全隔离数

这一节给出圈和圈的笛卡尔积的全隔离数的上界。

定理5.1. 对于正整数 $n, m \geq 3$ ，当 $n \equiv 0 (\mod 3)$ 时， $C_{n} □ C_{m}$ 的全隔离数

$\frac{2 n}{3} \leq ι_{t} (C_{n} □ C_{m}) \leq {\begin{array}{l} \frac{2 m n}{9} & n \equiv 0 (\mod 6), m \equiv 0 (\mod 3); \\ \frac{2 m n + n}{9} & n \equiv 0 (\mod 6), m \equiv 1 (\mod 3); \\ \frac{2 m n + 2 n}{9} & n \equiv 0 (\mod 6), m \equiv 2 (\mod 3); \\ \frac{2 m n + 3 m}{9} & n \equiv 3 (\mod 6), m \equiv 0 (\mod 3); \\ \frac{2 m n + 3 m + n - 3}{9} & n \equiv 3 (\mod 6), m \equiv 1 (\mod 3); \\ \frac{2 m n + 3 m + 2 n - 6}{9} & n \equiv 3 (\mod 6), m \equiv 2 (\mod 3) . \end{array}$

当 $n \equiv 0 (\mod 3)$ 且 $m \equiv 0 (\mod 3)$ 或者 $n \equiv 3 (\mod 3)$ 且 $m \equiv 1 (\mod 3)$ 时，上界是紧的。

证明. 设 $G = C_{n} □ C_{m}$ 并且 $V (G) = {(i, j) | 1 \leq i \leq n, 1 \leq j \leq m}$ 。进一步设 $A_{i} = {(i, j) | 1 \leq j \leq m}$ 并且 $B_{j} = {(i, j) | 1 \leq i \leq n}$ ，则 $G [A_{i}] ≅ C_{m}$ 且 $G [B_{j}] ≅ C_{n}$ 。显然，根据引理3.1， $n \equiv 0 (\mod 3)$ 以及 $n, m \geq 3$ ， $ι_{t} (C_{n} □ C_{m}) \geq ι_{t} (P_{n} □ P_{3}) = \frac{2 n}{3}$ 。

当 $n = 6$ ， $m = 3$ 时， $ι_{t} (C_{6} □ C_{3}) = 4 = \frac{2 \times 6 \times 3}{9}$ 。

当 $n \equiv 0 (\mod 6)$ 且 $m \equiv 1 (\mod 3)$ 时，设 $S_{4} = {(i, j) | i \equiv 5 (\mod 6), j = m}$ ， $S_{5} = {(i, j) | i \equiv 2 (\mod 6), j = m}$ ， $S_{6} = {(i, j) | i \equiv 5 (\mod 6), j = m - 1}$ 。则 $S^{'} = (S \ S_{4}) \cup S_{5} \cup S_{6}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | S^{'} | \leq (ι_{t} (P_{3} □ P_{m}) + 1) \frac{n}{6} + ι_{t} (P_{3} □ P_{m + 1}) \frac{n}{6} \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) \frac{n}{6} + (2 ⌊ \frac{m + 1}{3} ⌋ + 1) \frac{n}{6} \\ = \frac{2 m n + n}{9} . \end{matrix}$

当 $n \equiv 0 (\mod 6)$ 且 $m \equiv 2 (\mod 3)$ 时，设 $S_{7} = {(i, j) | i \equiv 2 (\mod 6), j = m - 1}$ 。则 $S^{″} = S \cup S_{7}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | S^{″} | \leq ι_{t} (P_{3} □ P_{m}) \frac{n}{6} + ι_{t} (P_{3} □ P_{m + 1}) \frac{n}{6} + \frac{n}{6} \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) \frac{n}{6} + 2 ⌊ \frac{m + 1}{3} ⌋ \frac{n}{6} + \frac{n}{6} \\ = \frac{2 m n + 2 n}{9} . \end{matrix}$

当 $n \equiv 3 (\mod 6)$ 且 $m \equiv 0 (\mod 3)$ 时，设 $S_{8} = {(i, j) | i = n - 1, 1 \leq j \leq m}$ 。则 $D = S \cup S_{8}$ 是图G的一个全隔离集。因此，根据引理3.1得

当 $n = 3$ ， $m = 3$ 时， $ι_{t} (C_{3} □ C_{3}) = 3 = \frac{2 \times 3 \times 3 + 3 \times 3}{9}$ 。

当 $n \equiv 3 (\mod 6)$ 且 $m \equiv 1 (\mod 3)$ 时， $D^{'} = S^{'} \cup S_{8}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | D^{'} | \leq (ι_{t} (P_{3} □ P_{m}) + 1) \frac{n - 3}{6} + ι_{t} (P_{3} □ P_{m + 1}) \frac{n - 3}{6} + m \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) \frac{n - 3}{6} + (2 ⌊ \frac{m + 1}{3} ⌋ + 1) \frac{n - 3}{6} + m \\ = \frac{2 m n + 3 m + n - 3}{9} . \end{matrix}$

当 $n = 3$ ， $m = 4$ 时， $ι_{t} (C_{3} □ C_{4}) = 4 = \frac{2 \times 3 \times 4 + 3 \times 4 + 3 - 3}{9}$ 。

当 $n \equiv 3 (\mod 6)$ 且 $m \equiv 2 (\mod 3)$ 时， $D^{″} = S^{″} \cup S_{8}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | D^{″} | \leq ι_{t} (P_{3} □ P_{m}) \frac{n - 3}{6} + ι_{t} (P_{3} □ P_{m + 1}) \frac{n - 3}{6} + m + \frac{n - 3}{6} \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) \frac{n - 3}{6} + 2 ⌊ \frac{m + 1}{3} ⌋ \frac{n - 3}{6} + m + \frac{n - 3}{6} \\ = \frac{2 m n + 3 m + 2 n - 6}{9} . \end{matrix}$

由于 $C_{n} □ C_{m} ≅ C_{m} □ C_{n}$ ，所以当 $n \equiv 1 (\mod 3)$ 时， $C_{n} □ C_{m}$ 的全隔离数只需考虑 $m \equiv 1$ 或 $2 (\mod 3)$ 的情况。

定理5.2. 对于正整数 $n, m \geq 3$ ，当 $n \equiv 1 (\mod 3)$ 且 $m \equiv 1$ 或 $2 (\mod 3)$ 时， $C_{n} □ C_{m}$ 的全隔离数

$\frac{2 n - 2}{3} \leq ι_{t} (C_{n} □ C_{m}) \leq {\begin{array}{l} \frac{2 m n + n - 2 m - 1}{9} + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ & m \equiv 1 (\mod 3), \\ \frac{2 m n - 2 m + 2 n - 2}{9} + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ & m \equiv 2 (\mod 3) . \end{array}$

证明. 设 $G = C_{n} □ C_{m}$ 并且 $V (G) = {(i, j) | 1 \leq i \leq n, 1 \leq j \leq m}$ 。进一步设 $A_{i} = {(i, j) | 1 \leq j \leq m}$ 并且 $B_{j} = {(i, j) | 1 \leq i \leq n}$ ，则 $G [A_{i}] ≅ C_{m}$ 且 $G [B_{j}] ≅ C_{n}$ 。显然，根据引理3.1， $n \equiv 1 (\mod 3)$ 以及 $n, m \geq 3$ ， $ι_{t} (C_{n} □ C_{m}) \geq ι_{t} (P_{n} □ P_{3}) = \frac{2 n - 2}{3}$ 。

当 $n \equiv 1 (\mod 3)$ 且 $m \equiv 1 (\mod 3)$ 时，设 $S_{1} = {(i, j) | i \equiv 2 (\mod 6), j \equiv 0 (\mod 3)}$ ， $S_{2} = {(i, j) | i \equiv 5 (\mod 6), j \equiv 1 (\mod 3)}$ ， $S_{3} = {(i, j) | i, j \equiv 2 (\mod 3)}$ ， $S_{4} = {(i, j) | i \equiv 5 (\mod 6), j = m}$ ， $S_{5} = {(i, j) | i \equiv 5 (\mod 6), j = m - 1}$ ， $S_{6} = {(i, j) | i \equiv 2 (\mod 6), j = m}$ ， $S_{7} = {(i, j) | i = n, j \equiv 2 or 3 (\mod 4)} \cup {(n, m - 1)}$ 。设 $S = S_{1} \cup S_{2} \cup S_{3}$ ， $S^{'} = (S \ S_{4}) \cup S_{5} \cup S_{6} \cup S_{7}$ 是图G的一个全隔离集。因此，根据引理3.1和定理3.1得

$\begin{matrix} ι_{t} (G) \leq | S^{'} | \leq (ι_{t} (P_{3} □ P_{m}) + 1) ⌈ \frac{n - 1}{6} ⌉ + ι_{t} (P_{3} □ P_{m + 1}) ⌊ \frac{n - 1}{6} ⌋ + γ_{t} (P_{m}) \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) ⌈ \frac{n - 1}{6} ⌉ + 2 ⌊ \frac{m + 1}{3} ⌋ ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ + ⌊ \frac{n - 1}{6} ⌋ \\ = \frac{2 m n + n - 2 m - 1}{9} + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ . \end{matrix}$

当 $n \equiv 1 (\mod 3)$ 且 $m \equiv 2 (\mod 3)$ 时，设 $S_{8} = {(i, j) | i \equiv 2 (\mod 6), j = m - 1}$ 。则 $S^{″} = S \cup S_{8} \cup S_{7}$ 是图G的一个全隔离集。因此，根据引理3.1和定理3.1得

$\begin{matrix} ι_{t} (G) \leq | S^{″} | \leq ι_{t} (P_{3} □ P_{m}) ⌈ \frac{n - 1}{6} ⌉ + ι_{t} (P_{3} □ P_{m + 1}) ⌊ \frac{n - 1}{6} ⌋ + γ_{t} (P_{m}) + ⌈ \frac{n - 1}{6} ⌉ \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) ⌈ \frac{n - 1}{6} ⌉ + 2 ⌊ \frac{m + 1}{3} ⌋ ⌊ \frac{n - 1}{6} ⌋ + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ + ⌈ \frac{n - 1}{6} ⌉ \\ = \frac{2 m n - 2 m + 2 n - 2}{9} + ⌊ \frac{m}{2} ⌋ + ⌈ \frac{m}{4} ⌉ - ⌊ \frac{m}{4} ⌋ . \end{matrix}$

由于 $C_{n} □ C_{m} ≅ C_{m} □ C_{n}$ ，所以当 $n \equiv 2 (\mod 3)$ 时， $C_{n} □ C_{m}$ 的全隔离数只需考虑 $m \equiv 2 (\mod 3)$ 的情况。

定理5.3. 对于正整数 $n, m \geq 3$ ，当 $n \equiv 2 (\mod 3)$ 且 $m \equiv 2 (\mod 3)$ 时， $C_{n} □ C_{m}$ 的全隔离数

$\frac{2 n - 1}{3} \leq ι_{t} (C_{n} □ C_{m}) \leq \frac{2 m n + 2 m + 2 n + 2}{9}$ 。

证明. 设 $G = C_{n} □ C_{m}$ 并且 $V (G) = {(i, j) | 1 \leq i \leq n, 1 \leq j \leq m}$ 。进一步设 $A_{i} = {(i, j) | 1 \leq j \leq m}$ 并且 $B_{j} = {(i, j) | 1 \leq i \leq n}$ ，则 $G [A_{i}] ≅ C_{m}$ 且 $G [B_{j}] ≅ C_{n}$ 。显然，根据引理3.1， $n \equiv 2 (\mod 3)$ 以及 $n, m \geq 3$ ， $ι_{t} (C_{n} □ C_{m}) \geq ι_{t} (P_{n} □ P_{3}) = \frac{2 n - 1}{3}$ 。

当 $n \equiv 2 (\mod 3)$ 且 $m \equiv 2 (\mod 3)$ 时，设 $S_{1} = {(i, j) | i \equiv 2 (\mod 6), j \equiv 0 (\mod 3)}$ ， $S_{2} = {(i, j) | i \equiv 5 (\mod 6), j \equiv 1 (\mod 3)}$ ， $S_{3} = {(i, j) | i, j \equiv 2 (\mod 3)}$ ， $S_{4} = {(i, j) | i \equiv 2 (\mod 6), j = m - 1}$ 。则 $S = S_{1} \cup S_{2} \cup S_{3} \cup S_{4}$ 是图G的一个全隔离集。因此，根据引理3.1得

$\begin{matrix} ι_{t} (G) \leq | S | \leq ι_{t} (P_{3} □ P_{m}) ⌈ \frac{n + 1}{6} ⌉ + ι_{t} (P_{3} □ P_{m + 1}) ⌊ \frac{n + 1}{6} ⌋ + ⌈ \frac{n + 1}{6} ⌉ \\ = (2 ⌊ \frac{m}{3} ⌋ + 1) ⌈ \frac{n + 1}{6} ⌉ + 2 ⌊ \frac{m + 1}{3} ⌋ ⌊ \frac{n + 1}{6} ⌋ + ⌈ \frac{n + 1}{6} ⌉ \\ = \frac{2 m n + 2 m + 2 n + 2}{9} . \end{matrix}$

6. 总结与开放性问题

本文根据全隔离数的定义给出了路和圈的笛卡尔积的全隔离数的上下界并证明了部分界是紧的。全隔离数作为部分控制(Partial Domination)理论的一个重要分支，其研究有助于深化对图控制理论的理解。路和圈的笛卡尔积是构造网格(grids)和环网(tori)等基本网络拓扑结构的基础模型。因此，研究这些图的全隔离数不仅具有理论价值，也为分析和设计具有特定容错性或监控能力的计算机网络、传感器网络等提供了理论参考。

问题6.1. 确定 $P_{n} □ P_{m}$ 、 $C_{n} □ P_{m}$ 以及 $C_{n} □ C_{m}$ 全隔离数的精确值。

致谢

在此，我们衷心感谢国家自然科学基金对本研究的资助与支持，同时也向所有为本研究提供指导与帮助的专家、老师和同学致以诚挚的谢意。特别感谢允许我们转载、引用相关资料的文献作者，正是基于您们的前期贡献与无私分享，才使得本研究得以顺利开展并取得成果。最后，谨向所有在科研道路上给予我们启发与支持的学者和同仁们表示最深切的感激。

基金项目

受国家自然科学基金(批准号：12261074、12461065)和青海师范大学中青年科研基金(编号：2025QZR11)资助。

NOTES

^*通讯作者。

参考文献

[1]	Caro, Y. and Hansberg, A. (2017) Partial Domination—The Isolation Number of a Graph. Filomat, 31, 3925-3944. https://doi.org/10.2298/fil1712925c
[2]	Lemańska, M., Souto-Salorio, M.J., Dapena, A. and Vazquez-Araujo, F.J. (2021) Isolation Number versus Domination Number of Trees. Mathematics, 9, Article 1325. https://doi.org/10.3390/math9121325
[3]	Lemańska, M., Mora, M. and Souto-Salorio, M.J. (2024) Graphs with Isolation Number Equal to One Third of the Order. Discrete Mathematics, 347, Article ID: 113903. https://doi.org/10.1016/j.disc.2024.113903
[4]	Boyer, G. and Goddard, W. (2024) Disjoint Isolating Sets and Graphs with Maximum Isolation Number. Discrete Applied Mathematics, 356, 110-116. https://doi.org/10.1016/j.dam.2024.05.022
[5]	张刚. 图的孤立[D]: [硕士学位论文]. 乌鲁木齐: 新疆大学, 2021.
[6]	Cao, Y., An, X. and Wu, B. (2025) Total Isolation of K-Cliques in a Graph. Discrete Mathematics, 348, Article ID: 114689. https://doi.org/10.1016/j.disc.2025.114689
[7]	Borg, P., Fenech, K. and Kaemawichanurat, P. (2022) Isolation of K-Cliques II. Discrete Mathematics, 345, Article ID: 112641. https://doi.org/10.1016/j.disc.2021.112641
[8]	Wei, X., Zhang, G. and Zhao, B. (2023) On the C4-Isolation Number of a Graph. arXiv: 2310.17337.
[9]	Cui, Q. and Zhang, J. (2023) A Sharp Upper Bound on the Cycle Isolation Number of Graphs. Graphs and Combinatorics, 39, Article No. 117. https://doi.org/10.1007/s00373-023-02717-w
[10]	Zhang, G. and Wu, B. (2024) On the Cycle Isolation Number of Triangle-Free Graphs. Discrete Mathematics, 347, Article ID: 114190. https://doi.org/10.1016/j.disc.2024.114190
[11]	Chen, J. and Xu, S. (2023) p5-Isolation in Graphs. Discrete Applied Mathematics, 340, 331-349. https://doi.org/10.1016/j.dam.2023.07.018
[12]	Zhang, G. and Wu, B. (2024) k-Isolation in graphs. Discrete Applied Mathematics, 357, 99-111. https://doi.org/10.1016/j.dam.2024.06.005
[13]	Boutrig, R. and Chellali, M. (2017) Total Vertex-Edge Domination. International Journal of Computer Mathematics, 95, 1820-1828. https://doi.org/10.1080/00207160.2017.1343469
[14]	Ahangar, H.A., Chellali, M., Sheikholeslami, S.M., et al. (2021) Total Vertex-Edge Domination in Trees. Acta Mathematica Universitatis Comenianae, 90, 127-143.
[15]	Senthilkumar, B., Naresh Kumar, H. and Venkatakrishnan, Y.B. (2020) A Lower Bound on the Total Vertex-Edge Domination Number of a Tree. Discrete Mathematics, Algorithms and Applications, 13, Article ID: 2050091. https://doi.org/10.1142/s1793830920500913
[16]	Singhwal, N. and Reddy, P.V.S. (2021) Total Vertex-Edge Domination in Graphs: Complexity and Algorithms. Discrete Mathematics, Algorithms and Applications, 14, Article ID: 2250031. https://doi.org/10.1142/s1793830922500318
[17]	Boyer, G., Goddard, W. and Henning, M.A. (2024) On Total Isolation in Graphs. Aequationes mathematicae, 99, 623-633. https://doi.org/10.1007/s00010-024-01057-1
[18]	Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer.
[19]	Haynes, T.W., Hedetniemi, S.T. and Henning, M.A. (2023) Domination in Graphs: Core Concepts. Springer.

为你推荐

友情链接