几类特殊图的孤立数

doi:10.12677/aam.2025.141020

期刊菜单

几类特殊图的孤立数
Isolation Number of Several Special Graphs

DOI: 10.12677/aam.2025.141020, PDF, HTML, XML,
作者: 阿不都艾再孜·乌不力哈斯木, 买吐肉孜·买司地克^*：新疆师范大学数学科学学院，新疆乌鲁木齐
关键词: 孤立集；孤立数；特殊图；平面格子图；Isolation Set； Isolation Number； Special Graphs； Plane Grid Graphs

摘要: 图的孤立集是顶点集的子集使得图中减去它的闭领域后剩下部分构成孤立点集，图的孤立数是图中最小孤立集的基数。孤立数相关概念在日常生活中起着重要的作用，如在流行病学中，可以用来评估孤立措施的有效性；在网络安全领域，孤立数的概念可以用于识别和孤立异常行为或潜在的威胁等。本文确定友谊图、风车图、轮图、风筝图以及杠铃图等几类特殊图的孤立数，并讨论平面格子图的孤立数。

Abstract: The isolation set of a graph is a subset of the vertex set such that the remaining part after subtracting its closed neighborhood from the graph constitutes an isolated vertex set, and the isolation number of a graph is the cardinality of the smallest isolated set in the graph. The concept of isolation numbers plays an important role in daily life, such as in epidemiology, where it can be used to evaluate the effectiveness of isolation measures; in the field of cybersecurity, the concept of isolation numbers can be used to identify and isolate abnormal behavior or potential threats. This article determines the isolation numbers of several special types of graphs, such as friendship graphs, windmill graphs, wheel graphs, kite graphs, and barbell graphs, and discusses the isolation numbers of plane grid graphs.

文章引用：阿不都艾再孜·乌不力哈斯木, 买吐肉孜·买司地克. 几类特殊图的孤立数[J]. 应用数学进展, 2025, 14(1): 173-184. https://doi.org/10.12677/aam.2025.141020

1. 引言

近年来，图的控制理论因其较强的应用性在城市交通、网络安全、社交网络等领域得到了广泛的研究。而像流行病学、通信网络等领域，因其资源有限但仍需进行有效分配从而达到特定的控制目标，故很难通过图的控制理论来控制所有顶点，具有一定的局限性，因此2017年Caro和Hansberg [1]通过放松控制理论的部分条件首次引入“图的孤立(Isolation of graph)”的概念，即在不完全控制图中所有顶点的情况下，对其中部分的顶点进行控制，实现整个图的特定的孤立效果，从而提高控制效率，此研究扩展了图论中支配集的概念，引入了部分控制和孤立数的新视角，为图论领域提供了新的研究方向。

自图的孤立的定义提出后，在图论与组合优化、流行病学、通信网络、应急管理以及交通网络等领域中，图的控制理论得到了一定的发展，并取得了较为明显的成就。如2017年Caro和Hansberg [1]证明一个 $n (n > 3)$ 阶不同构于5圈 $C_{5}$ 的连通图G的孤立数 $ι (G) \leq \frac{n}{3}$ ，确定了孤立数的精确界限和计算方法，为之后的研究提供了新理论基础。2021年Lemańska等人[2]给出了孤立数和控制数之间等价的刻画，并证明 $n (n \geq 3)$ 阶路 $P_{n}$ 的孤立数 $ι (P_{n}) = ⌈ \frac{n - 1}{4} ⌉$ ，扩展了孤立数和控制数的理论基础，还为网络安全和通信网络分析等实际应用领域提供了新的分析方法，推动了孤立数和控制数在图论领域的研究进展。2024年Lemańska等人[3]又对图的孤立数等于其顶点数的三分之一的特殊图进行了特征划分，证明了至少有6个顶点的连通图都有三组不相交的隔离集，并且给出了隔离数等于顶点数三分之一的单圈图和块图的刻画，深化了对图的孤立数和控制数的理解。2024年Boyer和Goddard [4]证明了除了 $K_{2}$ 和 $C_{5}$ 之外，至少有3个顶点的连通图都存在三个不相交的隔离集，使得不被这三个集合完全控制的顶点构成一个独立集，利用Lemańska等人[3]引入的图族，确定了所有 $ι (G) = \frac{n}{3}$ 的图。除图的 $K_{2}$ 孤立得到了广泛研究之外，还有图的 $K_{1, k + 1}$ 孤立[5]、 $K_{k}$ 孤立[6] [7]、圈孤立[8]-[10]、k-路孤立[11]、k-星孤[12]等方面的问题也得到了比较深入的研究。随着网络科学和数据分析技术的发展，孤立数的相关研究将进一步拓展到更多新的领域。

本文首先确定友谊图、风车图、轮图、扇图、风筝图以及杠铃图等几类特殊图的孤立数，并讨论了部分平面格子图的孤立数。

2. 基本概念

令图 $G = (V (G), E (G))$ 是简单连通图，其中顶点集为 $V (G)$ ，边集为 $E (G)$ 。若 $u v \in E (G)$ ，则u和v相邻；与u相邻的所有的顶点构成u的邻集，记 $N (u)$ ；u的闭邻域 $N [u]$ 是它与它的邻集的并，即 $N [u] = {u} \cup N (u)$ ；一个集合D的闭邻域 $N [D] = \underset{u \in D}{\cup} N [u]$ 。

定义1 ([1]). 设D是简单图 $G (V, E)$ 的顶点子集，若 $V (G) - N [D]$ 的导出子图是无边图，则称D为图G的孤立集，图G中最小孤立集的基数称为图G的孤立数，记为 $ι (G)$ ；如果顶点 $v \in D$ ，则v称作控制点。

定义2. 具有一个公共顶点的 $n (n \geq 2)$ 个三长圈 $C_{3}$ 构成的图称为友谊图(如图1所示)，表示为 $F_{3}^{n}$ 。

Figure 1. Friendship graph $F_{3}^{2}$ , $F_{3}^{3}$ , $F_{3}^{n}$

图1. 友谊图 $F_{3}^{2}$ ， $F_{3}^{3}$ ， $F_{3}^{n}$

定义3. 具有一个公共顶点的 $n (n \geq 2)$ 个四圈 $C_{4}$ 的并图称为风车图(如图2所示)，表示为 $D_{4}^{n}$ 。

Figure 2. Windmill graph $D_{4}^{2}$ , $D_{4}^{3}$ , $D_{4}^{n}$

图2. 风车图 $D_{4}^{2}$ ， $D_{4}^{3}$ ， $D_{4}^{n}$

定义4. 令由一个顶点v连接 $n - 1$ 阶圈 $C_{n - 1}$ 的每一个顶点得到的图称为轮图(如图3所示)，表示为 $W_{n}$ 。

Figure 3. Wheel graph $W_{n}$

图3. 轮图 $W_{n}$

定义5. 令由一个公共顶点v连接 $n - 1$ 阶路 $P_{n - 1}$ 的每一个顶点得到的图称为扇图(如图4所示)，表示为 $F_{n}$ 。

Figure 4. Fan graph $F_{n}$

图4. 扇图 $F_{n}$

定义6. 令由一个完全图 $K_{a}$ 连接路 $P_{b + 1}$ 得到的图称为风筝图，其中 $V (K_{a}) \cap V (P_{b + 1}) = 1$ (如图5所示)，a和b + 1分别为完全图 $K_{a}$ 和路 $P_{b + 1}$ 的阶，表示为 $L_{a, b}$ 。

Figure 5. Kite graph $L_{a, b}$

图5. 风筝图 $L_{a, b}$

定义7. 令由一条路 $P_{b + 2}$ 连接两个互不相交的圈 $C_{a}$ 和 $C_{c}$ 得到的图称为杠铃图(如图6所示)，其中b + 2，的a和c分别为路 $P_{b + 2}$ 、圈 $C_{a}$ 和 $C_{c}$ 的阶，表示为 $D_{a, b, c}$ 。

Figure 6. Barbell graph $D_{a, b, c}$

图6. 杠铃图 $D_{a, b, c}$

定义8. 设G和H是两个简单图， $G □ H$ 表示为图G和H的笛卡尔积，其顶点集和边级分别为

$V (G □ H) = V (G) \times V (H)$ ，

$E (G □ H) = {(u, v) (u^{'}, v^{'}) : v = v^{'} 且 u u^{'} \in E (G), u = u^{'} 且 v v^{'} \in E (H)}$ 。

定义9. 令由两条的路 $P_{m}$ 和 $P_{n}$ 作笛卡尔积得到的图称为平面格子图(如图7所示)，其中m和n分别为路 $P_{m}$ 和 $P_{n}$ 的阶，表示为 $P_{m} □ P_{n}$ 。

Figure 7. Grid graph $P_{6} □ P_{6}$

图7. 平面格子图 $P_{6} □ P_{6}$

定义10. 平面格子图 $P_{m + k} □ P_{n}$ 是两个平面格子图 $P_{m} □ P_{n}$ 和 $P_{k} □ P_{n}$ 的一个拼接(如图8所示)，表示为

$P_{m + k} □ P_{n} = (P_{m} + P_{k}) □ P_{n} = P_{m} □ P_{n} + P_{k} □ P_{n}$ 。

Figure 8. $P_{2} □ P_{6} + P_{4} □ P_{6} = P_{6} □ P_{6}$ , $P_{4} □ P_{2} + P_{4} □ P_{4} = P_{4} □ P_{6}$

图8. $P_{2} □ P_{6} + P_{4} □ P_{6} = P_{6} □ P_{6}$ ， $P_{4} □ P_{2} + P_{4} □ P_{4} = P_{4} □ P_{6}$

3. 友谊图、风车图、轮图、扇图、风筝、杠铃图的孤立数

定理1. 友谊图 $F_{3}^{n}$ 、风车图 $D_{4}^{n}$ 、轮图 $W_{n}$ 、扇图 $F_{n}$ 的孤立数为

$ι (F_{3}^{n}) = ι (D_{4}^{n}) = ι (W_{n}) = ι (F_{n}) = 1$ 。

证明. 由定义可知，友谊图、风车图、轮图、扇图中最大度顶点到其他顶点的距离最多为2，距离等于2的点本身构成独立集。因此，将上述四个图中最大度顶点删除即可，看图9，即 $V (G) - N [v]$ 的导出子图为无边图，其中v是最大度顶点。因此 $ι (F_{3}^{n}) = ι (D_{4}^{n}) = ι (W_{n}) = ι (F_{n}) \leq 1$ 。根据孤立数的定义，有边图的孤立数大于等于1，故 $ι (F_{3}^{n}) = ι (D_{4}^{n}) = ι (W_{n}) = ι (F_{n}) \geq 1$ 。所以 $ι (F_{3}^{n}) = ι (D_{4}^{n}) = ι (W_{n}) = ι (F_{n}) = 1$ 。

□

Figure 9. The domination vertex of friendship graph, windmill graph, wheel graph and fan graph

图9. 友谊图、风车图、轮图和扇图的控制点

定理2 ([2]). 一条有 $n (n \geq 3)$ 个顶点的路如果 $P_{n}$ 的孤立数为

$ι (P_{n}) = ⌈ \frac{n - 1}{4} ⌉$ 。

定理3. 风筝图 $L_{a, b}$ 的孤立数为

$ι (L_{a, b}) = 1 + ⌈ \frac{b - 2}{4} ⌉$ 。

证明. 因为风筝图 $L_{a, b}$ 是由一个完全图 $K_{a}$ 和 $b + 1$ 阶路 $P_{b + 1}$ 组成，首先，根据孤立数的概念，可得完全图的孤立数为1，即 $ι (K_{a}) = 1$ 。再由引理2可知，一条n阶路 $P_{n}$ 的孤立数为 $ι (P_{n}) = ⌈ \frac{n - 1}{4} ⌉$ ，所以在风筝图 $L_{a, b}$ 中，删除完全图 $K_{a}$ 和路 $P_{b + 1}$ 的唯一公共点 $v_{1}$ 后，再计算路 $P_{b + 1}$ 的孤立点即可。结合孤立数的定义可知，删除公共顶点 $v_{1}$ 时会连带删去路 $P_{b + 1}$ 的一个邻点，因此只需讨论路 $P_{b - 1}$ 的孤立数即可。

由此

$\begin{matrix} ι (D_{a, b, c}) = ι (K_{a}) + ι (P_{b - 1}) \\ = 1 + ⌈ \frac{(b - 1) - 1}{4} ⌉ \\ = 1 + ⌈ \frac{b - 2}{4} ⌉ \end{matrix}$

□

定理4. 有 $n (n \geq 5)$ 个顶点圈 $C_{n}$ 的孤立数为

$ι (C_{n}) = 1 + ⌈ \frac{n - 4}{4} ⌉$ 。

证明. 一个n阶圈 $C_{n}$ 去掉任意一个顶点后可变成 $n - 1$ 阶的路 $P_{n - 1}$ ，所以只需要计算出 $P_{n - 1}$ 的孤立数即可，结合孤立数的定义可知，删除圈中任意一个顶点时，会将该顶点的左右两个邻点连带删除，因此只需讨论路 $P_{n - 3}$ 的孤立数即可。

由此

$\begin{matrix} ι (C_{n}) = 1 + ι (P_{n - 3}) \\ = 1 + ⌈ \frac{(n - 3) - 1}{4} ⌉ \\ = 1 + ⌈ \frac{n - 4}{4} ⌉ \end{matrix}$

□

定理5：杠铃图 $D_{a, b, c}$ 的孤立数为

$ι (D_{a, b, c}) = 2 + ⌈ \frac{a - 4}{4} ⌉ + ⌈ \frac{b - 3}{4} ⌉ + ⌈ \frac{c - 4}{4} ⌉$ 。

证明. 因为杠铃图 $D_{a, b, c}$ 是由两个不相交的圈 $C_{a}$ 和 $C_{C}$ 连接 $b + 2$ 阶的路 $P_{b + 2}$ 组成。由定理4易得圈 $C_{a}$ 和 $C_{C}$ 的孤立数。再由引理2可知，一条n阶路 $P_{n}$ 的孤立数为 $ι (P_{n}) = ⌈ \frac{n - 1}{4} ⌉$ ，因此在杠铃图 $D_{a, b, c}$ 中先删除两个不相交的圈 $C_{a}$ 和 $C_{C}$ 分别与路 $P_{b + 2}$ 的两个公共顶点，再分别求出 $C_{a}$ 、 $C_{C}$ 和 $P_{b + 2}$ 的孤立数后求和即为杠铃图的孤立数。结合孤立数的定义可知，删除公共顶点时会连带删除路 $P_{b + 2}$ 的左右两个邻点，因此只需讨论路 $P_{b - 2}$ 的孤立数即可。

由此

$\begin{matrix} ι (D_{a, b, c}) = ι (C_{a}) + ι (P_{b - 2}) + ι (C_{c}) \\ = 1 + ⌈ \frac{a - 4}{4} ⌉ + ⌈ \frac{(b - 2) - 1}{4} ⌉ + 1 + ⌈ \frac{c - 4}{4} ⌉ \\ = 2 + ⌈ \frac{a - 4}{4} ⌉ + ⌈ \frac{b - 3}{4} ⌉ + ⌈ \frac{c - 4}{4} ⌉ \end{matrix}$

□

4. 平面格子图的孤立数

定理6. 平面格子图 $P_{2} □ P_{n}$ 的孤立数

$ι (P_{2} □ P_{n}) = ⌈ \frac{n}{3} ⌉ (n \geq 2)$ 。

证明. 先证 $ι (P_{2} □ P_{n}) \leq ⌈ \frac{n}{3} ⌉$ 。对n进行归纳，当 $n = 2$ ，有 $ι (P_{2} □ P_{2}) = 1 = ⌈ \frac{2}{3} ⌉$ ，即结论成立。

假设结论对大于等于2小于n的自然数成立。以下证对 $n (n \geq 3)$ 成立。由于 $P_{2} □ P_{n} = P_{2} □ P_{n - 2} + P_{2} □ P_{2}$ ， $ι (P_{2} □ P_{n}) \leq ι (P_{2} □ P_{n - 3}) + ι (P_{2} □ P_{3})$ 。根据归纳假设 $ι (P_{2} □ P_{n - 3}) \leq ⌈ \frac{n - 3}{3} ⌉$ ， $ι (P_{2} □ P_{3}) \leq 1$ 。所以

$ι (P_{2} □ P_{n}) \leq ⌈ \frac{n - 3}{3} ⌉ + 1 = ⌈ \frac{n}{3} ⌉$ 。

再证 $ι (P_{2} □ P_{n}) \geq ⌈ \frac{n}{3} ⌉$ 。设D是 $P_{2} □ P_{n}$ 的任何一个孤立集且 $| D | < ⌈ \frac{n}{3} ⌉$ ，则在 $P_{2} □ P_{n}$ 中至少存在某一个只含一个控制点的同构于 $P_{2} □ P_{4}$ 区域，这会导致图 $P_{2} □ P_{n} - N [D]$ 至少含一条边。这与孤立集定义矛盾，所以结论成立。

由此

$ι (P_{2} □ P_{n}) = ⌈ \frac{n}{3} ⌉$ 。

□

例1. 在图10中，我们展示 $P_{2} □ P_{2}$ 至 $P_{2} □ P_{9}$ 等8个图孤立集的分布，黑色点为控制点，白色点为被控制顶点，灰色为孤立顶点。可以从图中看出，当 $n \geq 4$ 时，每3个为一个循环增加一个控制点。

Figure 10. $ι (P_{2} □ P_{n}) (2 \leq n \leq 9)$

图10. $ι (P_{2} □ P_{n}) (2 \leq n \leq 9)$

定理7. 平面格子图 $P_{3} □ P_{n}$ 的孤立数

$ι (P_{3} □ P_{n}) = ⌊ \frac{n}{2} ⌋ (n \geq 2)$ 。

证明. 先证 $ι (P_{3} □ P_{n}) \leq ⌊ \frac{n}{2} ⌋$ 。对n进行归纳，当 $n = 2$ 时，有 $ι (P_{3} □ P_{2}) = 1 = ⌊ \frac{2}{2} ⌋$ ，即结论成立。

假设结论对大于等于2小于n的自然数成立。以下证对 $n (n \geq 3)$ 成立。由于 $P_{3} □ P_{n} = P_{3} □ P_{n - 2} + P_{3} □ P_{2}$ ， $ι (P_{3} □ P_{n}) \leq ι (P_{3} □ P_{n - 2}) + ι (P_{3} □ P_{2})$ 。根据归纳假设 $ι (P_{3} □ P_{n - 2}) \leq ⌊ \frac{n - 2}{2} ⌋$ ， $ι (P_{3} □ P_{2}) \leq 1$ 。所以

$ι (P_{3} □ P_{n}) \leq ⌊ \frac{n - 2}{2} ⌋ + 1 = ⌊ \frac{n}{2} ⌋$ 。

再证 $ι (P_{3} □ P_{n}) \geq ⌊ \frac{n}{2} ⌋$ 。设D是 $P_{3} □ P_{n}$ 的任何一个孤立集且 $| D | < ⌊ \frac{n}{2} ⌋$ ，则在 $P_{3} □ P_{n}$ 中至少存在某一个只含一个控制点的同构于 $P_{3} □ P_{4}$ 区域，这会导致图 $P_{3} □ P_{n} - N [D]$ 至少含一条边。这与孤立集定义矛盾，所以结论成立。

由此

$ι (P_{3} □ P_{n}) = ⌊ \frac{n}{2} ⌋$ 。

□

例2. 在图11中，我们展示 $P_{3} □ P_{2}$ 至 $P_{3} □ P_{7}$ 等7个图孤立集的分布。可以从图中看出，当 $n \geq 2$ 开始，每2个为一个循环增加一个控制点。

Figure 11. $ι (P_{3} □ P_{n}) (n \geq 2)$

图11. $ι (P_{3} □ P_{n}) (n \geq 2)$

定理8. 平面格子图 $P_{4} □ P_{n}$ 的孤立数

$ι (P_{4} □ P_{n}) = ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{4} ⌉ (n \geq 2)$ 。

证明. 图 $P_{4} □ P_{n} = P_{(3 + 1)} □ P_{n} = (P_{3} + P_{1}) □ P_{n} = P_{3} □ P_{n} + P_{n}$ ，由孤立数的定义，将图 $P_{4} □ P_{n}$ 分解成 $P_{3} □ P_{n} + P_{n}$ 后， $P_{3} □ P_{n}$ 与 $P_{n}$ 相连的首个顶点没有被孤立，所以计算时需要给 $P_{n}$ 增加一个顶点。

先证 $ι (P_{4} □ P_{n}) \leq ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{4} ⌉$ 。对n进行归纳，当 $n = 3$ 时，有：

$ι (P_{4} □ P_{3}) \leq ι (P_{3} □ P_{3}) + ι (P_{4}) = 1 + 1 = 2 = ⌊ \frac{3}{2} ⌋ + ⌈ \frac{3}{4} ⌉$ ，

即结论成立。

假设结论对大于等于2小于n的自然数成立。以下证对 $n (n \geq 4)$ 成立。由于 $P_{4} □ P_{n} = P_{3} □ P_{n} + P_{n + 1}$ ， $ι (P_{4} □ P_{n}) \leq ι (P_{3} □ P_{n}) + ι (P_{n + 1})$ 。根据定理6和引理2， $ι (P_{3} □ P_{n}) = ⌊ \frac{n}{2} ⌋$ ， $ι (P_{n + 1}) = ⌈ \frac{(n + 1) - 1}{4} ⌉ = ⌈ \frac{n}{4} ⌉$ 。所以

$ι (P_{4} □ P_{n}) \leq ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{4} ⌉$ 。

再证 $ι (P_{4} □ P_{n}) \geq ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{4} ⌉$ 。设D是 $P_{4} □ P_{n}$ 的任何一个孤立集且 $| D | < ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{4} ⌉$ ，则在 $P_{4} □ P_{n}$ 中至少存在某一个只含两个控制点的同构于 $P_{4} □ P_{4}$ 区域，这会导致图 $P_{4} □ P_{n} - N [D]$ 至少含一条边。这与孤立集定义矛盾，所以结论成立。

由此

$ι (P_{4} □ P_{n}) = ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{4} ⌉ (n \geq 2)$ 。

□

例3. 在图12中我们展示 $P_{4} □ P_{3}$ 至 $P_{4} □ P_{12}$ 等10个图孤立集的分布。可以从图中看出，它是由 $P_{3} □ P_{n}$ 和 $P_{n}$ 拼接得到的图。

Figure 12. $ι (P_{4} □ P_{n}) (3 \leq n \leq 12)$

图12. $ι (P_{4} □ P_{n}) (3 \leq n \leq 12)$

定理9. 平面格子图 $P_{5} □ P_{n}$ 的孤立数

$ι (P_{5} □ P_{n}) = ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{3} ⌉ (n \geq 3)$ 。

证明. 图 $P_{5} □ P_{n} = P_{(3 + 2)} □ P_{n} = (P_{3} + P_{2}) □ P_{n} = P_{3} □ P_{n} + P_{2} □ P_{n}$ 。

先证 $ι (P_{5} □ P_{n}) \leq ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{3} ⌉$ 。对n进行归纳，当 $n = 3$ 时，有：

$ι (P_{5} □ P_{3}) \leq ι (P_{3} □ P_{3}) + ι (P_{2} □ P_{3}) = 1 + 1 = 2 = ⌊ \frac{3}{2} ⌋ + ⌈ \frac{3}{3} ⌉$ ，

即结论成立。

假设结论对大于等于2小于n的自然数成立。以下证对 $n (n \geq 4)$ 成立。由于 $P_{5} □ P_{n} = P_{3} □ P_{n} + P_{2} □ P_{n}$ ， $ι (P_{5} □ P_{n}) \leq ι (P_{3} □ P_{n}) + ι (P_{2} □ P_{n})$ 。根据定理6和引理7， $ι (P_{3} □ P_{n}) = ⌊ \frac{n}{2} ⌋$ ， $ι (P_{2} □ P_{n}) = ⌈ \frac{n}{3} ⌉$ 。所以

$ι (P_{5} □ P_{n}) \leq ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{3} ⌉$ 。

再证 $ι (P_{5} □ P_{n}) \geq ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{3} ⌉$ 。设D是 $P_{5} □ P_{n}$ 的任何一个孤立集且 $| D | < ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{3} ⌉$ ，则在 $P_{5} □ P_{n}$ 中至少存在某一个只含两个控制点的同构于 $P_{5} □ P_{4}$ 区域，这会导致图 $P_{5} □ P_{n} - N [D]$ 至少含一条边。这与孤立集定义矛盾，所以结论成立。

由此

$ι (P_{5} □ P_{n}) = ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{3} ⌉$ 。

□

例4. 在图13中我们展示 $P_{5} □ P_{3}$ 至 $P_{4} □ P_{15}$ 等13个图孤立集的分布。可以从图中看出，它是由 $P_{3} □ P_{n}$ 和 $P_{2} □ P_{n}$ 拼接得到的图。

Figure 13. $ι (P_{5} \times P_{n}) (n \geq 3)$

图13. $ι (P_{5} \times P_{n}) (n \geq 3)$

5. 总结

本文根据孤立数的定义确定了扇图、轮图、完全图、风筝图、杠铃图以及部分平面格子图的孤立数。特殊图的孤立数研究不仅在理论上具有重要意义，而且在实际应用中也发挥着关键作用，特别是在化学分析、网络分析、社交网络研究、生物信息学等领域。通过研究这些特殊图的孤立数，我们可以更好地理解和利用这些图的结构特性，以解决实际问题。研究各类图的孤立数必定有着较为广阔的发展前景，也必将得到更进一步的研究和应用。

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]	Borg, P., Fenech, K. and Kaemawichanurat, P. (2020) Isolation of k-Cliques. Discrete Mathematics, 343, Article ID: 111879. https://doi.org/10.1016/j.disc.2020.111879
[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

为你推荐

友情链接