单和双圈图k-孤立数的上确界

Upper Bound on k-Isolation Number of Unicyclic and Bicyclic Graphs

摘要: 对一个自然数$k$ ，若简单无向图$G$ 的顶点子集$D$ 满足条件：减去$D$ 的闭邻域后得到的图$G-N\left[D\right]$ 不含$k+2$ 阶的星图$K_{1,k+1}$ 作为子图，则$D$ 被称为$G$ 的一个$k$ -孤立集。图$G$ 的最小一个$k$ -孤立集$D$ 的阶数被称为图$G$ 的$k$ -孤立数。本文得到了单和双圈图的$k$ -孤立数的上确界。

Abstract: For a natural number k, a vertex subset D of a simple undirected graph G satisfies the condition that the graph $G-N\left[D\right]$ obtained by removing the closed neighborhood of D does not contain the star graph $K_{1,k+1}$ of order $k+2$ as a subgraph, then it is calwled a k-isolating set of the graph. The minimum order of such a k-isolating set in a graph is referred to as the k-isolation number of the graph. This paper establishes the upper bound of the k-isolation numbers for unicyclic and bicyclic graphs.

1. 引言

图的控制理论是图论[1]中的经典研究方向之一，起源于20世纪60年代，最初用于建模通信网络中的关键节点识别问题。随着网络科学、人工智能和复杂系统的发展，控制理论被广泛应用于社交网络分析、传感器网络优化、病毒传播控制等领域。

传统的控制集[2]要求图中每个不在集合中的顶点至少有一个邻居在集合中，这一条件在某些实际应用中可能过于严格。为此，孤立集的概念被提出，作为控制理论的松弛形式。孤立集的核心思想是：通过移除某些顶点及其邻域，使得剩余子图不包含特定结构的子图(如完全图、圈、路径等)，从而实现对图结构的“隔离”或“破坏”。

如果D是控制集，则图G的一个顶点集合D满足不在D中的每个顶点至少有一个邻点在D中[2]。图G的控制数用$\gamma \left(G\right)$ 表示，是G的控制集的最小阶数。关于图的控制数理论，无数的专家和学者已有大量研究，可参阅书籍[3]及其参考文献。对于每个图$G=\left(V,E\right)$ ，定义点$v\in V$ 的闭邻域为$N_G\left[v\right]=\left\{v\right\}\cup \left\{u\in V:uv\in E\right\}$ 。点集$S\subseteq V$ 的闭邻域为$N_G\left[S\right]={\cup }_{v\in S}{N}_G\left[v\right]$ 。如果图G已经清楚，则可以简写为$N\left[u\right]$ 和$N\left[S\right]$ ，而不是$N_G\left[u\right]$ 和$N_G\left[S\right]$ 。用这种术语可以重新定义控制集的概念：D是G的控制集当且仅当$V=N\left[D\right]$ 。通过放松这个条件，可以引入孤立的概念。

要求$N[D]=V$ 在许多实际应用中非常重要。然而，有时这个条件并非必要或有利，此时可以考虑一个更宽松的条件。孤立集的概念就是这样一个例子。2017年，Caro和Hansberg [4]首次系统提出了孤立集的概念，并给出了若干基本性质与界。具体来说，对于一个图族$ℱ$ ，如果图G的一个顶点集合S满足从$V-N_G\left[S\right]$ 导出的子图中不包含$ℱ$ 中任何图的子图，则称S是$ℱ$ 孤立的。特别地，$K_1$ 孤立集就是通常的控制集。不在$K_2$ 孤立集控制下的顶点形成一个独立集，只有一些孤立点或者是空集。为了简化，用孤立集代替$K_2$ 孤立集。图G的孤立数$\iota \left(G\right)$ 是G的孤立集的最小阶数。2021年，Zhang [5]将$K_{1,k+1}$ -孤立数引入图的控制理论研究，提出了k-星孤立的概念，并研究了树、环、完全图等特殊图类的孤立数。其中值得注意的是，$K_2$ 孤立数等价于Lewis等人[6]更早提出的点-边控制数，进一步验证了孤立数的理论价值，亦与Canales等人[7]定义的2-距离顶点覆盖数相同，拓展了孤立数的应用范围。而早在1996年，文献[8]中已经出现了“移除顶点集及其邻域”的思想。

$K_{1,k+1}$ -孤立数作为控制理论的一个新兴分支，由Zhang [5]在2021年提出。图的孤立理论是图的控制理论的自然推广，代表着图论领域中一个极具创新性的研究趋势。本文对$K_{1,k+1}$ -孤立数的探讨仅是这一研究方向的初步尝试，预示着未来研究将更加深入并富有意义。$K_{1,k+1}$ -孤立数的引入不仅丰富了图论的理论体系，也为实际问题的解决提供了新的工具和方法，比如帮助设计更有效的网络结构，提高网络的鲁棒性和安全性，促进相关算法的设计和优化等。

本文的目的是证明两种图k孤立数的上界都是${\iota }_k\left(G\right)\le n/\left(k+3\right)$ 。接下来介绍一些术语和预备知识。

2. 预备知识

本文考虑的图均为简单无向连通图。设$G=\left(V,E\right)$ 表示顶点集为V，边集为E的简单图。对于任意$v\in V\left(G\right)$ ，用$d_G\left(v\right)$ 表示点v的度，有时简写为$d\left(v\right)$ ，即图G中与v关联的边数。设$C_m$ 和$P_n$ 分别表示m ($m\ge 3$ )阶圈和n ($n\ge 2$ )阶路。在图G中，点u和v之间的最短的$\left(u,v\right)$ 路的长称为u到v的距离，记为$d\left(u,v\right)$ 。图的直径就是图中任意两点之间最短路径的最大值，记为$diam\left(G\right)$ 。

图G的一个顶点称为叶子，如果它的度数为1；一个顶点称为支撑点，如果它与一个叶子相邻。设$\mathcal{T}$ 是一类树族，其定义如下：如果一棵树T属于$\mathcal{T}$ ，那么它可以通过在某一个树$T_0$ 的每个顶点v上连接一个$K_{1,k+1}$ 得到：通过一条边将v连接到$K_{1,k+1}$ 的一个叶子上。因此，如果T是一棵$n$ 阶属于$\mathcal{T}$ 的树，则$n$ 必为$k+3$ 的倍数。对于每个属于$\mathcal{T}$ 阶数至少为$2\left(k+3\right)$ 的树T，分别用$L\left(T\right)$ 、$S\left(T\right)$ 、$N\left(T\right)$ 和$R\left(T\right)$ 表示T的不属于$T_0$ 的叶子集合、支撑顶点集合、邻点集合(表示与支撑顶点相邻的非叶子点的集合)和剩余顶点集合(图1)。若$T\in \mathcal{T}$ ，则有$\left|R\right|=\left|N\right|=\left|S\right|=n/\left(k+3\right)$ ，$\left|L\right|=n-3n/\left(k+3\right)$ 。

Figure 1. $T\in \mathcal{T}$ and ${\iota }_k\left(T\right)=n/\left(k+3\right)$

图1. $T\in \mathcal{T}$ 且${\iota }_k\left(T\right)=n/\left(k+3\right)$

如果树T的阶数为$k+3$ ，且$T\in \mathcal{T}$ ，则$L\left(T\right)$ 是一个包含恰好一个叶子的集合，而$R\left(T\right)$ 是包含另一个叶子的集合。T的一个$\left(k+3\right)$ 集合是一个包含一个叶子、它的支撑顶点、与支撑顶点相邻的非叶子点以及与叶子最近的R中的顶点$k+3$ 个顶点的集合，对于任一$u\in V\left(T\right)$ ，用$T_{k+3}\left(u\right)$ 表示包含$u$ 的$\left(k+3\right)$ 集合，并且分别用$r\left(u\right)$ 、$n\left(u\right)$ 、$s\left(u\right)$ 和$l\left(u\right)$ 表示。注意，T的每个$K_{1,k+1}$ 孤立集D至少包含$\left(k+3\right)$ 集合中的一个顶点，$T_0$ 的所有顶点集合和所有邻点集合是$\mathcal{T}$ 的最小$K_{1,k+1}$ 孤立集。

为刻画极图，取一条t个顶点的路P，并将$K_{1,k+1}$ 的叶子依次与P的每个顶点相连构成树$\mathcal{T}$ 。显然P的顶点构成k-孤立集，且任何k-孤立集至少需从每个$K_{1,k+1}$ 中各取一个顶点，故

${\iota }_k\left(\mathcal{T}\right)=t=\frac{n}{k+3}$

因此界是紧的。

关于孤立的相关结论，已有以下结果。

Caro、Hansberg [4]和Zylinski [9]已经证明了以下孤立数的上界：

定理1 ([4] [9]). 设G是一个阶数为$n\ge 3$ 的连通图，且$G\ne C_5$ ，则$\iota \left(G\right)\le n/3$ ，并且这个上界是紧的。

2024年，Lemanska [10]和Boyer [11]等人刻画了$\iota \left(G\right)=n/3$ 时的极图，其中$\mathcal{G}$ ，$ℰ$ 分别是$\iota \left(G\right)=n/3$ 的单圈图族和14个特殊图。

定理2 ([10] [11]). 设G是一个阶数为n的连通图，$\iota \left(G\right)=n/3$ 当且仅当$G\in \mathcal{G}\cup ℰ$ 。

定理3 ([5]). 如果$G\notin \left\{P_3,C_3,C_6\right\}$ 是一个阶数为n的连通图，那么$\iota \left(G,K_{1,2}\right)\le 2n/7$ 。

定理4 ([4]). 设T是一棵有n个顶点的树，且T不同构于$K_{1,k+1}$ 。那么${\iota }_k\left(G\right)\le n/\left(k+3\right)$ ，并且这个上界是紧的。

此外，Zhang [12]、Borg [13]等人通过限定图结构，也获得了一系列更为精细的孤立数的界，并且控制数达到$n/2$ 上界的图已被刻画[14]，可描述为在给定图的每个顶点上粘合一个$K_2$ 而得到的图，此类图的结构特征启发了单、双圈图极图的构造。

3. 单圈图的上界

如果一个连通图G恰好包含一个圈，则称其为单圈图。单圈图在图论中具有重要地位，是树与圈图的过渡形式，常用于研究图的圈性质、控制性质、染色性质等。首先介绍一些术语和用于证明的相关引理。

定理5. 如果图G有一个支撑顶点v，使得其除了一个顶点外的所有邻点都是叶子，则存在一个最小k-孤立集，既不包含v，也不包含与v相邻的叶子。

证明. 令w是与v相邻且不是叶子点的唯一顶点。令D是G的一个最小的k-孤立集。如果D不包含$N\left[v\right]\backslash \left\{w\right\}$ 中的任何顶点，则D满足所需的条件。否则，考虑集合$D^{\prime }=\left(D\backslash N\left[v\right]\right)\cup \left\{w\right\}$ 。那么，$D^{\prime }$ 也是一个k-孤立集且$\left|D^{\prime }\right|\le \left|D\right|$ 。因此，$D^{\prime }$ 是一个既不包含v，也不包含与v相邻的叶子点的G的最小的k-孤立集。

对于单圈图G，设C是G中唯一的圈。对于圈C中的每个顶点u，记$T\left(u\right)$ 为从G中移除与u相邻的圈C的边后包含u的连通分支。注意$T\left(u\right)$ 是一棵树，称其为G中u的悬挂树。

引理1：若单圈图或双圈图G存在支撑顶点$v$ 满足$d\left(v\right)\ge k+2$ ，则

${\iota }_k\left(G\right)\le \frac{n}{k+3}$ 。

证明. 设u为与v相邻的叶子，令$G^{\prime }=G-u$ 。

若$G^{\prime }$ 为$K_{1,k+1}$ 任意添加一条边构成的单圈图，则G为在$G^{\prime }$ 上加任意一条边的单圈图或在$G^{\prime }$ 的一条边上细分一次得到的单圈图；若$G^{\prime }$ 为$K_{1,k+1}$ 任意添加两条边构成的双圈图，则G为$G^{\prime }$ 上加任意两条边的双圈图或在$G^{\prime }$ 的两条边上细分一次得到的双圈图；此时v即为k-孤立集，且$n=k+3$ ，故

${\iota }_k\left(G\right)=1=\frac{n}{k+3}$

若$G^{\prime }$ 不属于上述情况，由归纳假设有

${\iota }_k\left(G^{\prime }\right)\le \frac{n-1}{k+3}$

由于$d\left(v\right)\ge k+1$ ，u为与v相邻的叶子，则顶点$u\notin D$ ，因此$G^{\prime }$ 的任意k-孤立集也是G的k-孤立集，于是

${\iota }_k\left(G\right)\le {\iota }_k\left(G^{\prime }\right)\le \frac{n-1}{k+3}<\frac{n}{k+3}$

得证。

接下来，在证明定理的多种情况下使用以下注记。

注记1. 如果e是图G的一条边，且D是$G-e$ 的一个k-孤立集，使得e的至少一个端点属于$N\left[D\right]$ ，则D也是G的k-孤立集。

定义1. 对于整数$k\ge 3$ ，定义单圈图族${\mathcal{U}}_1$ 如下：

顶点集$V\left({\mathcal{U}}_1\right)=V\left(K_{1,k+1}\right)$ ，边集$E\left({\mathcal{U}}_1\right)=E\left(K_{1,k+1}\right)\cup \left\{e\right\}$ ，其中e为在$K_{1,k+1}$ 的叶子点之间添加的一条新边。

该图阶数为$k+2$ ，恰含一个支撑顶点，且该支撑顶点本身即构成${\mathcal{U}}_1$ 的一个k-孤立集，故${\iota }_k\left({\mathcal{U}}_1\right)=1$ ，见图2。

Figure 2. $K_{1,k+1}+e\in {\mathcal{U}}_1$ and ${\iota }_k\left({\mathcal{U}}_1\right)=1$

图2. $K_{1,k+1}+e\in {\mathcal{U}}_1$ 且${\iota }_k\left({\mathcal{U}}_1\right)=1$

定义2. 对于整数$k\ge 3$ ，定义单圈图族${\mathcal{U}}_2$ 如下：

顶点集$V\left({\mathcal{U}}_2\right)=V\left(\mathcal{T}\right)$ ，边集$E\left({\mathcal{U}}_2\right)=E\left(\mathcal{T}\right)\cup \left\{e\right\}$ ，其中e为在$\mathcal{T}$ 的任意两点之间添加的一条新边使之构成单圈图(图3)。

Figure 3. $G\in {\mathcal{U}}_2$ and ${\iota }_k\left(G\right)=n/\left(k+3\right)$

图3. $G\in {\mathcal{U}}_2$ 且${\iota }_k\left(G\right)=n/\left(k+3\right)$

单圈图族${\mathcal{U}}_2$ 的构造方式是：取一条t个顶点的路P，并将$K_{1,k+1}$ 的叶子依次与P的每个顶点相连构成树$\mathcal{T}$ ，在$\mathcal{T}$ 上加任意一条边构成单圈图族${\mathcal{U}}_2$ ，其中包括对于任一一个单圈图$G_0$ ，将$K_{1,k+1}$ 的叶子点与$G_0$ 的每一个顶点通过一条边相连，或者是对于图4中的任意一图，通过一条边将其与$\mathcal{T}$ 的顶点相连，$K_1$ 与$K_{1,k+1}$ 叶子的4种连边方式如下图所示，有且仅有以下方式使得此类单圈图族的k-孤立数达到上界。

Figure 4. Four special unicyclic graphs

图4. 4种特殊的单圈图

定理6. 如果G是n阶不同构于${\mathcal{U}}_1$ 的单圈图，则${\iota }_k\left(G\right)\le n/\left(k+3\right)$ ，且这个界是紧的。

证明. 对G的顶点数进行归纳。令D是G的一个最小的k-孤立集。当$n\le k+2$ 时，G中不存在同构于${\mathcal{U}}_1$ 的子图，故${\iota }_k\left(G\right)=0\le n/\left(k+3\right)$ 成立。

现设$n\ge k+3$ ，且对任意阶数小于n且不属于${\mathcal{U}}_1$ 的单圈图结论成立。分两种情况讨论。

情形1：G存在支撑顶点v满足$d\left(v\right)\ge k+2$ 。由引理1得

${\iota }_k\left(G\right)\le \frac{n}{k+3}$

结论显然成立。

情形2：G的所有支撑顶点的度数均小于等于$k+1$ 。

此时G的直径至少为3，否则G将属于${\mathcal{U}}_1$ ，与假设矛盾。取直径路径$P=x_0{x}_1{x}_2\cdots x_d$ ($d\ge 3$ )。若$d=3$ ，则$x_1$ 即为k-孤立集，且

${\iota }_k\left(G\right)=1\le \frac{n}{k+3}$

设$d\ge 4$ 。若$x_3{x}_4$ 属于圈中任意一条边即$x_3{x}_4\in E\left(C\right)$ ，删去边$x_3{x}_4$ 得到树T满足

${\iota }_k\left(T\right)\le \frac{n}{k+3}$

又因为所有支撑顶点度数为$k+1$ ，$x_3{x}_4$ 是图G的一条边，若D是$G-\left\{x_3{x}_4\right\}$ 的一个k-孤立集，且$x_3{x}_4$ 的至少一个端点属于$N\left[D\right]$ ，那么D也是G的k-孤立集。于是

${\iota }_k\left(G\right)={\iota }_k\left(T\right)\le \frac{n}{k+3}$

若$x_3{x}_4$ 不属于圈中任意一条边即$x_3{x}_4\notin E\left(C\right)$ ，那么删去边$x_3{x}_4$ 得到两个图$G_1$ 和$G_2$ ，且$x_3\in G_1$ ，$x_4\in G_2$ 。

若$G_1$ 是单圈图，则$G_2$ 是一棵树即$T\left(x_4\right)$ ，满足

${\iota }_k\left(G_2\right)\le \frac{\left|V\left(G_2\right)\right|}{k+3}$

由于所有支撑顶点度数为$k+1$ ，$G_1$ 至少有$k+3$ 个顶点，则$x_3$ 是$G_1$ 的k-孤立集。那么

${\iota }_k\left(G\right)\le 1+{\iota }_k\left(G_2\right)\le \frac{\left|V\left(G_1\right)\right|}{k+3}+\frac{\left|V\left(G_2\right)\right|}{k+3}=\frac{n}{k+3}$

若$G_2$ 是单圈图，则$G_1$ 是一棵树即$T\left(x_3\right)$ ，满足

${\iota }_k\left(G_1\right)\le \frac{\left|V\left(G_1\right)\right|}{k+3}$

若$diam\left(G_2\right)\le 2$ ，则$x_3$ 是G的k-孤立集，结论成立；若$diam\left(G_2\right)\ge 3$ ，则$G_2\notin {\mathcal{U}}_1$ ，由归纳假设

${\iota }_k\left(G_2\right)\le \frac{\left|V\left(G_2\right)\right|}{k+3}$

取$G_2$ 的最小k-孤立集I，则$I\cup \left\{x_3\right\}$ 是G的k-孤立集，于是

${\iota }_k\left(G\right)\le 1+\left|I\right|\le \frac{\left|V\left(G_1\right)\right|}{k+3}+\frac{\left|V\left(G_2\right)\right|}{k+3}=\frac{n}{k+3}$

综上，不等式得证。

为证明紧性，按定义2构造单圈图族${\mathcal{U}}_2$ 。由图3、图4的结构可知，路径P或$G_0$ 的顶点集即构成G的一个k-孤立集；同时，任何k-孤立集必须至少从每个$K_{1,k+1}$ 中各取一个顶点。因此，

${\iota }_k\left(G\right)=t=\frac{n}{k+3}$

因此界是紧的。

如果$G\in {\mathcal{U}}_2$ ，那么取最上层的顶点集合就是图G的一个最小k-孤立集，所以有以下命题。

命题1. 如果G是一个n阶图，并且$G\in {\mathcal{U}}_2$ ，那么

${\iota }_k\left(G\right)=\frac{n}{k+3}$ 。

4. 双圈图的上界

对于一个连通图G，若图G满足$\left|E\left(G\right)\right|=\left|V\left(G\right)\right|+1$ ，则称G为双圈图，即是具有两个圈的连通图。设$B\left(G\right)$ 是G的一个双圈子图且$B\left(G\right)$ 不含悬挂点，则称$B\left(G\right)$ 为双圈图G的基图。注意到，根据两个圈之间的连接方式，双圈图主要可分为以下三种基本结构类型：$\infty$ -图、哑铃图和θ-图，即分别对应于图中的：$B_1\left(p,q\right)$ ($p\ge 3,q\ge 3$ )；$B_2\left(p,l,q\right)$ (其中$\left(p,l,q\right)$ 中至少有两个大于或等于2)；$B_3\left(P_s,P_l,P_m\right)$ ($s\ge 3,l\ge 3,m\ge 1$ )。有时简写为$B_1,B_2,B_3$ 。

1. 两个圈共享一个公共点：$B_1\left(p,q\right)$

这种结构中，两个圈$C_P$ 和$C_q$ 恰好有一个公共顶点，形如“$\infty$ ”字形。记作：$B_1\left(p,q\right)$ 。$\infty$ -图的特点是两个圈在一点相交，其他部分互不相交。如图5。

Figure 5. $B_1\left(p,q\right)$

图5. $B_1\left(p,q\right)$

2. 两个圈通过一条路径连接：$B_2\left(p,l,q\right)$

两个圈$C_P$ 和$C_q$ 之间通过一条长度至少为1的路径相连，路径的两个端点分别位于两个圈上。记作：$B_2\left(p,l,q\right)$ ，其中l是连接路径的长度。θ-图的特点是两个圈不直接相交，而是通过一条“桥”连接。如图6。

Figure 6. $B_2\left(p,l,q\right)$

图6. $B_2\left(p,l,q\right)$

3. 三条内部不相交的路径连接两个点：$B_3\left(P_s,P_l,P_m\right)$

这种结构由两个顶点x和y通过三条内部不相交的路径连接而成，形成一个“θ”形状。记作：$B_3\left(P_s,P_l,P_m\right)$ ，其中$m\le \min \left\{s,l\right\}$ 。θ-图的特点是两个顶点之间有三条不同的路径，形成一个闭合结构，包含两个圈。如图7。

Figure 7. $B_3\left(P_s,P_l,P_m\right)$

图7. $B_3\left(P_s,P_l,P_m\right)$

这三种结构构成了所有不含悬挂点的双圈图的基本类型，且彼此互斥，共同覆盖了所有可能的双圈图结构。

定义3. 对于整数$k\ge 3$ ，定义双圈图族${\mathcal{U}}_3$ 如下：

顶点集$V\left({\mathcal{U}}_3\right)=V\left(K_{1,k+1}\right)$ ，边集$E\left({\mathcal{U}}_3\right)=E\left(K_{1,k+1}\right)\cup \left\{e_1,e_2\right\}$ ，其中$e_1,e_2$ 为在$K_{1,k+1}$ 的叶子点之间添加的两条不同的边。

该图阶数为$k+2$ ，恰含一个支撑顶点，且该支撑顶点本身即构成${\mathcal{U}}_3$ 的一个k-孤立集，故${\iota }_k\left({\mathcal{U}}_3\right)=1$ 。

定义4. 对于整数$k\ge 3$ ，定义双圈图族${\mathcal{U}}_4$ 如下：

顶点集$V\left({\mathcal{U}}_4\right)=V\left(\mathcal{T}\right)$ ，边集$E\left({\mathcal{U}}_4\right)=E\left(\mathcal{T}\right)\cup \left\{e_1,e_2\right\}$ ，其中$e_1,e_2$ 为在$\mathcal{T}$ 的任意两点之间添加的两条不同的新边使之构成双圈图。

双圈图族${\mathcal{U}}_4$ 的构造方式分三种，第一种是将$K_{1,k+1}$ 的叶子点依次与$B_1,B_2,B_3$ 的每个顶点相连，第二种是在$\mathcal{T}$ 上加任意两条边构成双圈图族${\mathcal{U}}_4$ ，第三种是对于任一一个单圈图$G_0$ ，将${\mathcal{U}}_1$ 的顶点与$G_0$ 的一个顶点通过一条边相连，再将$K_{1,k+1}$ 的叶子点与$G_0$ 剩下的每一个顶点通过一条边相连。

定理7. 如果G是n阶不同构于${\mathcal{U}}_3$ 的双圈图，则${\iota }_k\left(G\right)\le n/\left(k+3\right)$ ，且这个界是紧的。

证明. 对G的顶点数进行归纳。令D是G的一个最小的k-孤立集。当$n\le k+2$ 时，G中不存在同构于${\mathcal{U}}_3$ 的子图，故${\iota }_k\left(G\right)=0\le n/\left(k+3\right)$ 成立。

现设$n\ge k+3$ ，且对任意阶数小于n且不同构于${\mathcal{U}}_3$ 的双圈图结论成立。

情形1：G存在支撑顶点v满足$d\left(v\right)\ge k+2$ 。由引理1得

${\iota }_k\left(G\right)\le \frac{n}{k+3}$

结论显然成立。

情形2：G的所有支撑顶点的度数均等于$k+1$ 。

此时G的直径至少为3，否则G将成为${\mathcal{U}}_3$ ，与假设矛盾。取直径路径$P=x_0{x}_1{x}_2\cdots x_d$ ($d\ge 3$ )。若$d=3$ ，则$x_1$ 即为k-孤立集，且

${\iota }_k\left(G\right)=1\le \frac{n}{k+3}$

设$d\ge 4$ 。若$x_3{x}_4$ 属于圈中任意一条边即$x_3{x}_4\in E\left(C\right)$ ，删去边$x_3{x}_4$ 得到单圈图$G^{″}$ 满足

${\iota }_k\left(G^{″}\right)\le \frac{n}{k+3}$

又因为所有支撑顶点度数为$k+1$ ，则$x_2$ 属于k-孤立集，且$x_3{x}_4$ 是图G的一条边，若D是$G-\left\{x_3{x}_4\right\}$ 的一个k-孤立集，那么$x_3{x}_4$ 的至少一个端点属于$N\left[D\right]$ ，D也是G的$k$ -孤立集。于是

${\iota }_k\left(G\right)={\iota }_k\left(G^{″}\right)\le \frac{n}{k+3}$

若$x_3{x}_4$ 不属于圈中任意一条边即$x_3{x}_4\notin E\left(C\right)$ ，那么删去边$x_3{x}_4$ 得到两个图$G_1$ 和$G_2$ ，且$x_3\in G_1$ ，$x_4\in G_2$ 。

若$G_1$ 是双圈图，则$G_2$ 是一棵树即$T\left(x_4\right)$ ，满足

${\iota }_k\left(G_2\right)\le \frac{\left|V\left(G_2\right)\right|}{k+3}$

由于所有支撑顶点度数为$k+1$ ，$G_1$ 至少有$k+3$ 个顶点，则$x_3$ 是$G_1$ 的k-孤立集。那么

${\iota }_k\left(G\right)\le 1+{\iota }_k\left(G_2\right)\le \frac{\left|V\left(G_1\right)\right|}{k+3}+\frac{\left|V\left(G_2\right)\right|}{k+3}=\frac{n}{k+3}$

若$G_2$ 是双圈图，则$G_1$ 是一棵树即$T\left(x_3\right)$ ，满足

${\iota }_k\left(G_1\right)\le \frac{\left|V\left(G_1\right)\right|}{k+3}$

若$\dim \left(G_2\right)\le 2$ ，则$x_3$ 是G的k-孤立集，结论成立；若$\dim \left(G_2\right)\ge 3$ ，则$G^{\prime }\notin {\mathcal{U}}_3$ ，由归纳假设

${\iota }_k\left(G_2\right)\le \frac{\left|V\left(G_2\right)\right|}{k+3}$

取$G_2$ 的最小k-孤立集I，则$I\cup \left\{x_3\right\}$ 是G的k-孤立集，于是

${\iota }_k\left(G\right)\le 1+\left|I\right|\le \frac{\left|V\left(G_1\right)\right|}{k+3}+\frac{\left|V\left(G_2\right)\right|}{k+3}=\frac{n}{k+3}$

若$G_1$ 是单圈图，则$G_2$ 也是单圈图，$G_1$ 至少有$k+3$ 个顶点，则$x_3$ 是$G_1$ 的k-孤立集，$x_3{x}_4\in E\left(N\left[D\right]\right)$ 。又由于所有支撑顶点度数为$k+1$ ，那么

${\iota }_k\left(G\right)\le 1+{\iota }_k\left(G_2\right)\le \frac{\left|V\left(G_1\right)\right|}{k+3}+\frac{\left|V\left(G_2\right)\right|}{k+3}=\frac{n}{k+3}$

综上，不等式得证。

此外，为证明紧性，按定义4构造双圈图族${\mathcal{U}}_4$ 。由构造可知，$B_1,B_2,B_3$ 或路径P或$G_0$ 的顶点集即构成G的一个k-孤立集，且任何k-孤立集必须至少从每个$K_{1,k+1}$ 中各取一个顶点。因此，

${\iota }_k\left({\mathcal{U}}_4\right)=t=\frac{n}{k+3}$

因此界是紧的。

如果$G\in {\mathcal{U}}_4$ ，那么取最上层的顶点集合就是图G的一个最小k-孤立集，所以有以下命题。

命题2. 如果G是一个n阶图，并且$G\in {\mathcal{U}}_4$ ，那么

${\iota }_k\left(G\right)=\frac{n}{k+3}$ 。

5. 开放性问题与未来展望

尽管本文给出了单圈图与双圈图k-孤立数的紧上界，但k-孤立理论整体上仍处于起步阶段，大量结构性与算法性的问题尚待解决。下面给出5个开放性问题，供后续研究参考。

问题1. 如果G是n阶连通图，则k-孤立数的上界是多少？

问题2. 若G为最大度不超过t的图。给定$k,t\in N$ ，是否存在仅依赖于k与t的常数$c\left(k,t\right)$ ，使得

${\iota }_k\left(G\right)\le c\left(k,t\right)\cdot \frac{n}{k+1}$

对任意$G\in {\mathcal{G}}_t$ 成立？

问题3. 对固定$k\ge 1$ ，给定图G与整数s，判定${\iota }_k\left(G\right)\le s$ 的问题是否为NP-完全？

问题4. 对经典的随机图$\mathcal{G}\left(n,p\right)$ 问题，研究${\iota }_k\left(\mathcal{G}\left(n,p\right)\right)$ 的渐近阈值函数。

问题5. 对两个任意图$G,H$ ，${\iota }_k\left(G\square H\right)$ ${\iota }_k\left(G\right),{\iota }_k\left(H\right)$ 之间是否存在关系？

若是突破上述问题，不仅会丰富图控制与孤立理论本身，也将为网络鲁棒性、动态监测与信息传播阻断等实际应用提供新的理论支撑。

6. 总结

本文主要围绕单、双圈图的k-孤立数展开研究，给出了该参数的一个紧上界。通过引入k-孤立集的定义，并结合图的结构特征，本文证明了对于任意一个n阶不同构于${\mathcal{U}}_2$ 的单圈图和不同构于${\mathcal{U}}_4$ 的双圈图，其k-孤立数满足${\iota }_k\left(G\right)\le n/\left(k+3\right)$ ，并且该上界是紧的，最后提出了一些开放性问题和未来的研究方向。本文的研究不仅丰富了图的控制理论与孤立理论的内容，也为进一步研究其他图类的k-孤立数提供了思路和方法，未来的工作可以拓展到更一般的图类，如仙人掌图、随机图或具有特定度限制的图，探讨其孤立数的界与结构特征之间的关系，并结合算法设计与实际应用，推动图论理论与网络科学的深度融合。