K-独立性在树中的应用
《Discrete Applied Mathematics》:On k-independence in trees
【字体:
大
中
小
】
时间:2026年10月22日
来源:Discrete Applied Mathematics 1.1
编辑推荐:
**摘要**
对于图 $G$,若集合 $D \subseteq V(G)$ 使得 $V(G) \setminus D$ 中的每个顶点在 $D$ 中至少有一个邻居,则称 $D$ 为 $G$ 的支配集。对于任意正整数 $k$,若 $G[S]$ 的最大度小于 $k$,则称集合 $
**摘要**
对于图 $G$,若集合 $D \subseteq V(G)$ 使得 $V(G) \setminus D$ 中的每个顶点在 $D$ 中至少有一个邻居,则称 $D$ 为 $G$ 的支配集。对于任意正整数 $k$,若 $G[S]$ 的最大度小于 $k$,则称集合 $S \subseteq V(G)$ 为 $G$ 的 $k$-独立集。$G$ 的 $k$-独立数,记作 $\alpha_k(G)$,是 $G$ 中 $k$-独立集的最大基数。若集合 $I \subseteq V(G)$ 既是 $k$-独立集又是支配集,则称 $I$ 为 $G$ 的 $k$-独立支配集。$G$ 的 $k$-独立支配数,记作 $i_k(G)$,是 $G$ 中 $k$-独立支配集的最小基数。显然 $i_1(G) = i(G) \leq \alpha(G) = \alpha_1(G)$,其中 $i(G)$ 和 $\alpha(G)$ 分别为 $G$ 的通常意义的独立支配数和独立数。设 $T$ 为具有 $n \geq 2$ 个顶点的树。最近,Zhang 和 Wu 证明了 $i_2(T) \leq \frac{2}{3}\alpha_2(T)$,本文作者证明了 $i_3(T) \leq \frac{3}{5}\alpha_3(T)$,且两个界都是紧的。这些结果自然地引出了一个问题:对于一般的 $k \geq 4$,$i_k(T)$ 与 $\alpha_k(T)$ 之间是否存在类似的关系。在本文中,我们对这个问题给出了肯定的回答。对于每个 $k \geq 4$,我们证明了 $i_k(T) \leq \frac{k}{2k-1}\alpha_k(T)$,并刻画了所有使等号成立的极值树。
**引言**
在本文中,我们仅考虑有限、简单且无向图。对于图 $G$,我们用 $V(G)$ 和 $E(G)$ 分别表示 $G$ 的顶点集和边集。对于任意顶点 $v \in V(G)$,用 $d_G(v)$(无歧义时简记为 $d(v)$)表示 $v$ 在 $G$ 中的度。$G$ 的最大度记为 $\Delta(G)$。对于任意集合 $S \subseteq V(G)$,用 $G[S]$ 和 $G-S$ 分别表示 $G$ 中由 $S$ 和 $V(G) \setminus S$ 导出的子图。对于任意子图 $H \subseteq G$,我们常将 $G - V(H)$ 简写为 $G - H$。$G$ 的直径,记作 $\mathrm{diam}(G)$,是 $G$ 中任意一对顶点之间距离的最大值。$G$ 的直径路径是指长度等于 $G$ 的直径的路径。对于任意正整数 $k$,我们用 $[k]$ 表示集合 $\{1, 2, \ldots, k\}$。我们用 $A \eqcolon B$ 将 $B$ 重新命名为 $A$。
树 $T$ 的叶子是度为 1 的顶点,$T$ 的支撑点是与叶子相邻的顶点。$T$ 的叶子集和支撑点集分别记为 $L(T)$ 和 $S(T)$。对于有根树 $T$ 中的任意顶点 $v$,用 $C(v)$、$G(v)$ 和 $D(v)$ 分别表示 $v$ 的子节点集、孙子节点集和后代的集合,并用 $D[v] = D(v) \cup \{v\}$。此外,我们用 $L(v)$ 和 $R(v)$ 分别表示 $v$ 的度为 1 和度为 2 的子节点集合。$v$ 处的最大子树,记作 $T_v$,是由 $D[v]$ 在 $T$ 中导出的子树。用 $h(v)$ 表示 $v$ 与 $T_v$ 中顶点之间的最大距离。我们用 $P_n$ 和 $S_n$ 分别表示 $n$ 个顶点的路径和星。对于两个正整数 $r$ 和 $s$,双星 $DS_{r,s}$ 是恰好有两个非叶子顶点的树,其中一个顶点与 $r$ 个叶子相邻,另一个顶点与 $s$ 个叶子相邻。
设 $G$ 为一个图。若集合 $D \subseteq V(G)$ 使得 $V(G) \setminus D$ 中的每个顶点在 $D$ 中至少有一个邻居,则称 $D$ 为 $G$ 的支配集。$G$ 的支配数,记作 $\gamma(G)$,是 $G$ 中支配集的最小基数。若 $S \subseteq V(G)$ 中任意两个顶点不相邻,则称 $S$ 为 $G$ 的独立集。$G$ 的独立数,记作 $\alpha(G)$,是 $G$ 中独立集的最大基数。若集合 $I \subseteq V(G)$ 既是独立集又是支配集,则称 $I$ 为 $G$ 的独立支配集。$G$ 的独立支配数,记作 $i(G)$,是 $G$ 中独立支配集的最小基数。由上述定义可知,以下不等式链成立。
**观察 1.1** 对于任意图 $G$,$\gamma(G) \leq i(G) \leq \alpha(G)$。
支配及其实际应用已在文献中被广泛研究(见例如 [3], [14], [16], [18], [19], [20], [21], [24])。
$k$-独立的概念由 Fink 和 Jacobson [12], [13] 作为独立的自然推广而引入。设 $k$ 为正整数。若 $S$ 中每个顶点在 $S$ 中至多有 $k-1$ 个邻居(即 $\Delta(G[S]) < k$),则称集合 $S \subseteq V(G)$ 为 $G$ 的 $k$-独立集。$G$ 的 $k$-独立数,记作 $\alpha_k(G)$,是 $G$ 中 $k$-独立集的最大基数。若集合 $I \subseteq V(G)$ 既是 $k$-独立集又是支配集,则称 $I$ 为 $G$ 的 $k$-独立支配集。$G$ 的 $k$-独立支配数,记作 $i_k(G)$,是 $G$ 中 $k$-独立支配集的最小基数。显然 $\alpha_1(G) = \alpha(G)$ 且 $i_1(G) = i(G)$。为简洁起见,$G$ 中基数为 $\alpha_k(G)$ 的 $k$-独立集也称为 $\alpha_k(G)$-集,$G$ 中基数为 $i_k(G)$ 的 $k$-独立支配集也称为 $i_k(G)$-集。关于图中 $k$-独立性有许多有趣的结果,请参阅 [1], [2], [4], [5], [9], [10], [11], [15], [17]。
在本文中,我们主要研究树中 $k$-独立支配和 $k$-独立性相关的问题。2021年,Dehgardi 等人 [8] 研究了树中支配数、独立支配数和 2-独立数之间的关系,并证明了以下两个结果。
**定理 1.2** Dehgardi 等人 [8] 对于任意具有 $n \geq 2$ 个顶点的树 $T$,$i(T) \leq \frac{3}{4}\alpha_2(T)$。
**定理 1.3** Dehgardi 等人 [8] 对于任意具有 $n \geq 2$ 个顶点的树 $T$,$\gamma(T) + i(T) \leq \frac{4}{3}\alpha_2(T)$。
定理 1.2 和定理 1.3 后来分别由 Zhang 和 Wu [22] 以及本文作者 [7] 推广到任意正整数 $k$ 的 $k$-独立数。
**定理 1.4** Zhang 和 Wu [22] 设 $k$ 为正整数。对于任意具有 $n \geq 2$ 个顶点的树 $T$,$i(T) \leq \frac{k+1}{2k}\alpha_k(T)$。
**定理 1.5** Cui 和 Zou [7] 设 $k$ 为正整数。对于任意具有 $n \geq 2$ 个顶点的树 $T$,$\gamma(T) + i(T) \leq \frac{2k}{2k-1}\alpha_k(T)$。
受定理 1.2 的启发,Zhang 和 Wu [23] 还建立了树中 2-独立支配数与 2-独立数之间的类似关系。
**定理 1.6** Zhang 和 Wu [23] 对于任意具有 $n \geq 2$ 个顶点的树 $T$,$i_2(T) \leq \frac{2}{3}\alpha_2(T)$。
最近,本文作者 [6] 进一步推导了树中 3-独立支配数与 3-独立数之间的关系。
**定理 1.7** Cui 和 Zou [6] 对于任意具有 $n \geq 2$ 个顶点的树 $T$,$i_3(T) \leq \frac{3}{5}\alpha_3(T)$。
此外,定理 1.2、1.3、1.4、1.5、1.6 和 1.7 中的所有界都是紧的,并且相应的极值树已被刻画。
观察 1.1 以及定理 1.6 和定理 1.7 意味着,对于每个 $1 \leq k \leq 3$ 和每个具有 $n \geq 2$ 个顶点的树 $T$,$i_k(T) \leq \frac{k}{2k-1}\alpha_k(T)$。
这自然引出了一个问题:对于一般的 $k \geq 4$,同样的结论是否成立。在本文中,我们对这个问题给出了肯定的回答。在陈述主要结果之前,我们先介绍一个树族 $T_k$。
对于两个整数 $p, q$,其中 $p \geq 1$ 且 $0 \leq q \leq p$,蜘蛛 $S_{p,q}$ 是通过将星 $S_{p+1}$ 中的 $q$ 条边各细分一次所得到的树(见 Figure 1 的插图)。对于每个 $k \geq 4$,令 $T_k$ 为按如下方式递归定义的树族:
(a) $S_{k,k-1} \in T_k$;
(b) 若 $T' \in T_k$,则 $T \in T_k$,其中 $T$ 是将 $T'$ 的某个支撑点与 $S_{k,k-1}$(与 $T'$ 顶点不相交)的某个支撑点之间添加一条边所得到的树。
注意对于两个不同的 $k$ 和 $k'$,可能 $T_k \cap T_{k'} \neq \emptyset$。
现在我们可以陈述本文的主要结果。
**定理 1.8** 设 $k \geq 4$ 为整数。对于任意具有 $n \geq 2$ 个顶点的树 $T$,
$$i_k(T) \leq \frac{k}{2k-1}\alpha_k(T)$$
等号成立当且仅当 $T \in T_k$。
本文余下部分组织如下。在第 2 节中,我们给出后续所需的一些辅助结果。在第 3 节中,我们给出定理 1.8 的证明。
**初步结果**
在本节中,我们证明了一些初步结果,将在下一节中用于证明定理 1.8。为简洁起见,我们假设 $k$ 为 $k \geq 4$ 的整数。
**引理 2.1** 对于任意蜘蛛 $S_{p,q}$,$i_k(S_{p,q}) \leq \frac{k}{2k-1}\alpha_k(S_{p,q})$,等号成立当且仅当 $p = k$ 且 $q = k-1$(即 $S_{p,q} = S_{k,k-1}$)。
**证明** 由 $S_{p,q}$ 的定义可知:
$$i_k(S_{p,q}) = \begin{cases} q+1, & \text{若 } 0 \leq q \leq p-1 \\ q, & \text{若 } q = p \end{cases}$$
$$\alpha_k(S_{p,q}) = \begin{cases} p+q+1, & \text{若 } 1 \leq p \leq k-1 \\ p+q, & \text{若 } p \geq k \end{cases}$$
若 $0 \leq q \leq p-1$ 且 $1 \leq p \leq k-1$,则
$$i_k(S_{p,q}) = q+1 = \frac{k}{2k-1}(p+q+1) - \frac{k(p-q-1)+q+1}{2k-1} < \frac{k}{2k-1}(p+q+1) = \frac{k}{2k-1}\alpha_k(S_{p,q}).$$
**定理 1.8 的证明** 在本节中,我们证明定理 1.8。
**定理 1.8 的证明** 若 $T \in T_k$,则由引理 2.2(v) 和 (vi) 可得
$$i_k(T) = \frac{n}{2} = \frac{k}{2k-1} \cdot \frac{2k-1}{2k} \cdot n = \frac{k}{2k-1}\alpha_k(T).$$
下面,我们将通过对 $n$ 进行归纳来证明必要性。若 $2 \leq n \leq 4$,则 $T \in \{P_2, P_3, P_4, S_4\}$,容易验证定理的断言成立。因此我们可以假设 $n \geq 5$ 且定理对所有具有少于 $n$ 个顶点的非平凡树成立。
若 $\mathrm{diam}(T) = 2$,则 $T$ 是星 $S_n$。由于 $i_k(S_n) = 1$ 且 $\alpha_k(S_n) \geq n-1$,我们看到
$$i_k(S_n) = 1 < \frac{n-1}{2} < \frac{k}{2k-1}(n-1) \leq \frac{k}{2k-1}\alpha_k(S_n).$$
**致谢** 作者感谢匿名审稿人的仔细阅读和宝贵建议,这些建议改进了本文的呈现。本工作得到了国家自然科学基金(编号 12171239)的支持。
Qing Cui | Xu Zou