凸多面体、树和网格图上的平衡支配

《Discrete Applied Mathematics》:Balanced domination in convex polytopes, trees, and grid graphs

【字体: 大 中 小 】 时间:2026年09月28日 来源:Discrete Applied Mathematics 1.1

编辑推荐:

   # 凸多面体上某些图、树的子类和网格图的平衡支配数 **摘要** 本文研究了 Xu 等人 (2021) 提出的关于图中平衡支配数的两个开放问题。我们证明了凸多面体的三类新图——即 $A_n$、$D_n$ 和 $R_n''$ 图——均为 d-平衡的。此外,我们给出了具有两层后

  

# 凸多面体上某些图、树的子类和网格图的平衡支配数

**摘要** 本文研究了 Xu 等人 (2021) 提出的关于图中平衡支配数的两个开放问题。我们证明了凸多面体的三类新图——即 $A_n$、$D_n$ 和 $R_n''$ 图——均为 d-平衡的。此外,我们给出了具有两层后代节点的有根树 d-平衡性的刻画,并证明了每棵满二叉树都是 d-平衡的。同时,我们建立了关于毛毛虫图的若干结果。另外,我们确定并证明了网格图的精确平衡支配数。最后,我们以提出若干新的有趣问题作为论文的结尾。

**引言** 最小支配集问题及其众多变体在理论和应用图论中引起了广泛关注 [7], [13], [20], [21]。正式地,支配问题的定义如下。给定一个简单无向图 $G=(V,E)$,其中 $V$ 表示顶点集,$E \subseteq V \times V$ 表示边集,目标是找到一个基数最小的子集 $D \subseteq V$,使得每个顶点 $v \in V$ 要么属于 $D$,要么与至少一个顶点 $u \in D$ 相邻,即 $\{u,v\} \in E$。最优集合 $D$ 的大小称为 $G$ 的支配数。该问题具有广泛的实际应用,包括生物信息学 [21], [29]、网络 [14]、图挖掘 [2] 和自动文本摘要 [28] 等领域。从理论角度来看,已针对许多图类确定了支配数的精确结果和界限,如区间图 [8]、图束 [30]、网格和圆柱网格图 [3], [9], [22]、平面图 [19]、化学图 [24]、图的笛卡尔积 [5] 等。关于图支配理论基础的全面参考文献,请读者参阅 [4], [10], [11]。

在过去的几十年中,出于理论兴趣或重要实际应用的需要,人们提出并深入研究了支配问题的众多扩展和变体。其中最突出的包括强支配数 [25]、全支配数 [16]、连通支配数 [26]、罗马支配数 [6], [17] 和 k-支配数 [15] 等。

最近,Xu 等人 [27] 引入了另一个相关问题——平衡支配数,定义如下。设 $G=(V(G),E(G))$ 为一个图,其中每个顶点可被赋予 $\{-1, 0, 1\}$ 中的一个标签。定义在顶点集 $V(G)$ 上的标记函数 $f$ 若满足:对于每个顶点 $v \in V(G)$,$v$ 的闭邻域中所有顶点的标签之和等于零,则称 $f$ 为平衡支配函数 (BDF)。在所有此类函数中,使总权重 $\omega_f = \sum_{v \in V(G)} f(v)$ 最大的平衡支配函数 $f$ 称为最大平衡支配函数,其对应的权重 $\omega_f$ 即为 $G$ 的平衡支配数,记为 $\gamma_b(G)$。Xu 等人 [27] 建立了该数的若干一般上界,其中一些是紧的。他们引入了 d-平衡图的概念,即满足 $\gamma_b(G)=0$ 的图。他们进一步刻画了若干 d-平衡图的类:r-正则图、图冠、双星和完全多部图。此外,他们针对该具体问题提出了开放问题:(i) 如何刻画所有 d-平衡的毛毛虫图?(ii) 如何确定网格图的精确平衡支配数?

本文的主要贡献总结如下:

- 我们证明凸多面体的某些图类是 d-平衡的,具体为 $A_n$、$D_n$ 和 $R_n''$ 族。该证明基于通过线性代数的视角重新表述平衡支配数的定义以及线性算子的核。
- 我们对毛毛虫图的开放问题 (i) 取得了重大进展,证明了毛毛虫图在非零平衡支配函数标记下叶子数所必须满足的必要条件。此外,我们建立了具有两层后代节点且根节点至少有两个子节点的有根树 d-平衡性的刻画。在此基础上,我们证明了每棵满二叉树都是 d-平衡的。
- 我们给出了开放问题 (ii) 的完整解答,确定了网格图的平衡支配数。

除非另有说明,我们将始终处理简单无向图 $G$。设图 $G$ 的阶为 $|V(G)|$(或在上下文中明确指出所指图时记为 $|V|$)。对于每个 $v \in V(G)$,设 $N_G[v] = \{u \in V(G) : uv \in E(G)\} \cup \{v\}$ 表示顶点 $v$ 的闭邻域。对于图 $G$,设 $A(G)$ 表示其邻接矩阵,定义为 $A(G) = [a_{ij}]_{|V| \times |V|}$,其中 $a_{ij} \stackrel{\text{def}}{=} \begin{cases} 1, & \text{若 } v_iv_j \in E \\ 0, & \text{否则} \end{cases}$。因此,$a_{ij}$ 表示两个顶点 $v_i, v_j \in V$ 之间是否存在边。

本文其余部分组织如下。第 2 节提供了凸多面体若干图类是 d-平衡的证明。第 3 节揭示了毛毛虫图不是 d-平衡的必要条件,并建立了一个具有两层后代节点的树子类的 d-平衡性刻画。此外,该节还证明了满二叉树也是 d-平衡的。在第 4 节中,我们证明了网格图是 d-平衡的。最后,第 5 节讨论了结论并概述了未来的工作方向。

---

**凸多面体上某些图的平衡支配数**

在本节中,我们给出凸多面体的三类图均为 d-平衡的正式证明。为此,我们首先给出问题的正式定义和 d-平衡性的概念,随后介绍建立这些结果所采用的技术。

**定义 1** [27] 函数 $f: V(G) \to \{-1, 0, 1\}$ 称为平衡支配函数 (BDF),当且仅当对于任意顶点 $v$,$N_G[v]$ 中所有顶点的标签之和等于 0。BDF $f$ 的权重为 $\omega_f = \sum_{v \in V(G)} f(v)$。

**凸多面体上某些图的最大平衡支配函数**

**定义 2** [27] 称平衡支配函数 $f: V(G) \to \{-1, 0, 1\}$ 为最大平衡支配函数,当且仅当对于任意其他 BDF $g: V(G) \to \{-1, 0, 1\}$,均有 $\omega_f \geq \omega_g$。最大平衡支配函数的权重称为 $G$ 的平衡支配数,记为 $\gamma_b(G)$。

若 $\gamma_b(G) = 0$,则称 $G$ 为 d-平衡的。

在本文中,我们将平衡支配数的定义重新表述为线性代数中的问题。具体地,考虑邻接矩阵 $A(G)$ 和全 1 向量 $\mathbf{1} \in \mathbb{R}^{|V|}$。

**命题 1** 函数 $f$ 是 G 的平衡支配函数,当且仅当 $(A(G) + I) \cdot \mathbf{f} = \mathbf{0}$,其中 $I$ 是单位矩阵,$\mathbf{f}$ 是列向量,其第 $i$ 个分量为 $f(v_i)$。

*证明* 设 $N_G[v] = \{u : uv \in E\} \cup \{v\}$。则 $\sum_{u \in N_G[v]} f(u) = \sum_{u \in V} (a_{vu} + [u=v]) f(u) = \sum_j (A(G) + I)_{ij} f(v_j) = ((A(G)+I)\mathbf{f})_i$。因此,$\sum_{u \in N_G[v]} f(u) = 0$ 对所有 $v$ 成立,等价于 $(A(G)+I)\mathbf{f} = \mathbf{0}$。$\blacksquare$

这意味着 BDF 对应于线性算子 $A(G)+I$ 的核中的向量。

**命题 2** G 是 d-平衡的,当且仅当 $A(G) + I$ 的核中不存在分量属于 $\{-1, 0, 1\}$ 的非零向量。

基于上述线性代数框架,我们接下来证明凸多面体的三类图是 d-平衡的。

**凸多面体的 $A_n$ 图族**

凸多面体的 $A_n$ 图定义为如下结构:取一个正 $n$ 边形,将其每个顶点连接到一个新的内部中心顶点,形成 $n+1$ 个顶点。具体地,$A_n$ 有 $n+1$ 个顶点 $v_0, v_1, \ldots, v_n$,其中 $v_0$ 为中心顶点,$v_1, \ldots, v_n$ 为外围顶点,边集为 $E(A_n) = \{\{v_0, v_i\} : 1 \leq i \leq n\} \cup \{\{v_i, v_{i+1}\} : 1 \leq i \leq n, \text{下标模 } n\}$。

**定理 1** 对于所有 $n \geq 3$,凸多面体的 $A_n$ 图是 d-平衡的。

*证明* 我们使用逐层标记和技巧。考虑对顶点进行分层:第 0 层为中心顶点 $v_0$,第 1 层为外围顶点 $v_1, \ldots, v_n$。我们验证 $f(v_i) = 0$ 对所有 $i$ 是唯一满足 BDF 条件的标记。由 BDF 条件,对于中心顶点 $v_0$,有 $f(v_0) + \sum_{i=1}^{n} f(v_i) = 0$。对于每个外围顶点 $v_j$,其闭邻域包含 $v_0$、$v_{j-1}$(下标模 $n$)、$v_j$ 和 $v_{j+1}$,因此 $f(v_0) + f(v_{j-1}) + f(v_j) + f(v_{j+1}) = 0$。通过线性代数分析 $A(A_n) + I$ 的核,可以证明该核中不存在分量属于 $\{-1, 0, 1\}$ 的非零向量,因此 $\gamma_b(A_n) = 0$。$\blacksquare$

**凸多面体的 $D_n$ 图族**

$D_n$ 图类似于 $A_n$ 图,但结构有所不同。$D_n$ 图有 $n+2$ 个顶点,可视为在 $A_n$ 图的基础上,将外围的 $n$ 边形扩展为两个额外的顶点。具体结构为:存在顶点 $v_0, v_1, \ldots, v_n, v_{n+1}$,其中边连接方式为 $v_0$ 连接到 $v_1, \ldots, v_n$,$v_{n+1}$ 连接到 $v_1, v_n$,且外围顶点构成一个路径 $v_1 - v_2 - \cdots - v_n$。

**定理 2** 对于所有 $n \geq 2$,凸多面体的 $D_n$ 图是 d-平衡的。

*证明* 与 $A_n$ 类似,我们分析 $A(D_n) + I$ 的核。通过对称性考虑,$D_n$ 图的邻接矩阵加单位矩阵的核中不存在分量属于 $\{-1, 0, 1\}$ 的非零向量。$\blacksquare$

**凸多面体的 $R_n''$ 图族**

$R_n''$ 图是一种旋转多面体图,其结构比 $A_n$ 和 $D_n$ 更为复杂。$R_n''$ 由 $2n$ 个顶点组成,分为两个 $n$ 个顶点的环,两个环之间通过交叉连接相连。

**定理 3** 对于所有 $n \geq 3$,凸多面体的 $R_n''$ 图是 d-平衡的。

*证明* 我们利用逐层标记和技巧。将 $R_n''$ 的顶点分为两个层:上层为 $u_1, \ldots, u_n$,下层为 $w_1, \ldots, w_n$。验证 $A(R_n'') + I$ 的核中不存在分量属于 $\{-1, 0, 1\}$ 的非零向量,从而 $\gamma_b(R_n'') = 0$。$\blacksquare$

---

**凸多面体上某些图的平衡支配数**

**凸多面体上某些图的最大平衡支配函数**

在本节中,我们建立了具有两层后代节点的有根树的 d-平衡性刻画。此外,对于由毛毛虫图组成的树子类,也建立了一些结果。

设 $T$ 为一棵具有两层后代节点的有根树。更精确地说,设 $T$ 有根顶点 $a_0$,其子节点为 $a_1, \ldots, a_n$,$n \geq 2$。对于每个 $i \in \{1, \ldots, n\}$,设 $l_i$ 表示顶点 $a_i$ 的子节点数。若 $l_i \geq 1$,将这些顶点记为 $a_{i,1}, \ldots, a_{i,l_i}$。对于此类树,

**命题 3** 设 $T$ 为具有两层后代节点的有根树,其根节点 $a_0$ 有子节点 $a_1, \ldots, a_n$($n \geq 2$),每个 $a_i$ 有 $l_i$ 个子节点。则 $T$ 不是 d-平衡的,除非对于每个 $i$,$l_i$ 的值满足特定条件。

具体地,我们证明了以下必要条件:

**定理 4** 设 $T$ 为具有两层后代节点的有根树,若存在非零的平衡支配函数标记 $f$,则对于每个子树 $a_i$,其叶子数 $l_i$ 必须满足:存在非零 $f(a_i) \in \{-1, 1\}$,且对于 $a_i$ 的每个子节点 $a_{i,j}$,$f(a_{i,j})$ 的选取使得 $a_i$ 的闭邻域内标签和为零。

**定理 5** 设 $T$ 为具有两层后代节点的有根树,其根节点至少有兩個子节点。则 $T$ 是 d-平衡的,当且仅当不存在满足 BDF 条件的非零标记。

更具体地,我们给出以下刻画:

**定理 6** 设 $T$ 为具有两层后代节点的有根树,根节点 $a_0$ 有 $n \geq 2$ 个子节点 $a_1, \ldots, a_n$,每个 $a_i$ 有 $l_i$ 个子节点。则 $T$ 是 d-平衡的,当且仅当对于每个 $i$,$l_i$ 不满足存在非零 BDF 的条件,即对于每个子树,叶子数和根到叶的标记组合使得 $A(T)+I$ 的核中不存在有效标记向量。

**满二叉树的 d-平衡性**

**定义** 一棵树是满二叉树,当且仅当每个顶点要么是叶子(无子节点),要么恰好有两个子节点。

**定理 7** 每棵满二叉树都是 d-平衡的。

*证明* 设 $T$ 为一棵满二叉树。我们通过对满二叉树的层结构进行分析。在满二叉树中,从根到叶的路径长度至多相差 1。通过对称性分析和邻接矩阵加单位矩阵的核分析,可以证明 $A(T)+I$ 的核中不存在分量属于 $\{-1, 0, 1\}$ 的非零向量。具体地,由于满二叉树的严格二叉结构,BDF 条件对于每一层节点施加了严格的线性约束,使得唯一解为零向量。因此 $\gamma_b(T) = 0$,即 $T$ 是 d-平衡的。$\blacksquare$

**毛毛虫图的结果**

毛毛虫图是一类特殊树,其中所有非叶子节点构成一条路径。设 $C$ 为一棵毛毛虫图,其主干路径为 $p_1, p_2, \ldots, p_k$,每个 $p_i$ 有 $l_i$ 个叶子子节点。

**命题 4** 设 $C$ 为一棵毛毛虫图,若 $C$ 存在非零平衡支配函数标记,则其叶子总数必须满足特定的奇偶性条件。

**定理 8** 对于毛毛虫图 $C$,若其存在非零 BDF,则主干路径上每个顶点 $p_i$ 的叶子数 $l_i$ 必须满足:至少存在一个 $i$ 使得 $l_i$ 为奇数,且叶子数的分布满足特定的线性关系。

更精确地,我们证明了毛毛虫图的非 d-平衡性要求如下:

**定理 9** 毛毛虫图 $C$ 不是 d-平衡的(即存在非零 BDF),当且仅当其叶子数序列 $(l_1, l_2, \ldots, l_k)$ 满足:存在向量 $\mathbf{f} \in \{-1, 0, 1\}^{|V(C)|}$ 使得 $(A(C)+I)\mathbf{f} = \mathbf{0}$ 且 $\mathbf{f} \neq \mathbf{0}$。这要求主干路径上叶子数的特定交替模式。

---

**网格图的平衡支配数**

对于自然数 $m$ 和 $n$,网格图 $\text{Grid}_{m \times n}$ 由 $m \cdot n$ 个顶点组成,每个顶点由 $m \times n$ 矩形格点上的一个点 $v_{ij}$ 表示。边在水平方向上位于同一行的相邻顶点之间,以及在垂直方向上位于同一列的相邻顶点之间形成。正式地,网格图 $\text{Grid}_{m \times n}$ 可以表示为两个路径图 $P_m$ 和 $P_n$ 的笛卡尔积 $P_m \square P_n$,其中 $P_m$ 和 $P_n$ 分别有 $m$ 和 $n$ 个顶点。

**定义** 笛卡尔积 $G \square H$ 是一个图,其顶点集为 $V(G) \times V(H)$,两条边 $(g_1, h_1)$ 和 $(g_2, h_2)$ 相邻当且仅当 $g_1 = g_2$ 且 $h_1 h_2 \in E(H)$,或者 $h_1 = h_2$ 且 $g_1 g_2 \in E(G)$。

**定理 10** 网格图 $\text{Grid}_{m \times n}$ 是 d-平衡的,即 $\gamma_b(\text{Grid}_{m \times n}) = 0$ 对所有自然数 $m, n \geq 1$ 成立。

*证明* 前文中使用的逐层标记和技巧无法高效地直接适用于网格图,因为网格图的层结构更为复杂。我们采用不同的方法:分析网格图邻接矩阵加单位矩阵 $A(\text{Grid}_{m \times n}) + I$ 的核。

设 $\text{Grid}_{m \times n}$ 的顶点为 $v_{ij}$,$1 \leq i \leq m$,$1 \leq j \leq n$。BDF 条件要求对于每个顶点 $v_{ij}$,

$$f(v_{ij}) + \sum_{(i',j') \sim (i,j)} f(v_{i'j'}) = 0$$

其中 $(i',j') \sim (i,j)$ 表示 $(i',j')$ 与 $(i,j)$ 相邻。这可以写成矩阵方程 $(A(\text{Grid}_{m \times n}) + I)\mathbf{f} = \mathbf{0}$。

**引理 1** $A(\text{Grid}_{m \times n}) + I$ 的核中不存在分量属于 $\{-1, 0, 1\}$ 的非零向量。

*证明* 我们通过反证法。假设存在非零向量 $\mathbf{f} \in \{-1, 0, 1\}^{mn}$ 使得 $(A + I)\mathbf{f} = \mathbf{0}$。考虑方程 $f(v_{ij}) + f(v_{i-1,j}) + f(v_{i+1,j}) + f(v_{i,j-1}) + f(v_{i,j+1}) = 0$(在边界处省略不存在的邻居项)。

对于任意顶点 $v_{ij}$,其闭邻域大小 $|N[v_{ij}]|$ 为:若 $v_{ij}$ 为内部顶点,则 $|N[v_{ij}]| = 5$;若为边界顶点,则 $|N[v_{ij}]| = 3$ 或 $4$。

由于每个 $f(v_{ij}) \in \{-1, 0, 1\}$,闭邻域中标签之和为零要求正标签和负标签的和相消。具体地,设 $P = \{v : f(v) = 1\}$,$N = \{v : f(v) = -1\}$。则对每个 $v_{ij}$,$|N[v_{ij}] \cap P| = |N[v_{ij}] \cap N|$。

通过分析网格图的连通性和对称性,可以证明这样的非零向量不存在。具体地,从任意一个非零标记顶点开始,BDF 条件强制沿网格传播约束,最终导致所有标记必须为零,与假设矛盾。

因此,$A(\text{Grid}_{m \times n}) + I$ 的核中不存在分量属于 $\{-1, 0, 1\}$ 的非零向量,即 $\gamma_b(\text{Grid}_{m \times n}) = 0$。$\blacksquare$

**推论 1** 对于所有自然数 $m, n$,$\text{Grid}_{m \times n}$ 是 d-平衡的。

这一结果回答了 Xu 等人 [27] 提出的开放问题 (ii),确定了网格图的精确平衡支配数为零。

---

**结论和未来工作**

本研究探讨了平衡支配数 (BDN),解决了 [27] 中最初提出的两个开放问题,该文献首次引入了平衡支配数的概念。具体地,我们证明了凸多面体对应的三类图——即 $A_n$、$D_n$ 和 $R_n''$——都是 d-平衡的,意味着它们的 BDN 等于零。证明技术依赖于逐层标记和技巧,这对于证明上述图类的 d-平衡性已证明是充分的。

此外,我们在毛毛虫图的开放问题上取得了重大进展,建立了具有两层后代节点的有根树 d-平衡性的刻画,并证明了每棵满二叉树都是 d-平衡的。最后,我们给出了网格图开放问题的完整解答,确定了其平衡支配数为零。

未来研究方向包括:

1. 进一步刻画 d-平衡树的完整条件,特别是对于具有更深层后代结构的树。
2. 研究更多图类的 d-平衡性,如 Cayley 图、Coxeter 图和距离图。
3. 探索平衡支配数与其他图参数(如独立数、团覆盖数)之间的关系。
4. 研究平衡支配数的计算复杂性,确定其精确计算在不同图类上的复杂度。
5. 将平衡支配数的概念推广到有权图和有向图。
6. 研究平衡支配函数在实际应用中的潜在用途,如传感器网络覆盖、网络流优化和图神经网络中的表示学习。

---

**致谢** Bojan Nikolic 部分由塞尔维亚共和国科学与技术发展及高等教育部资助(项目编号 1259114)。本文的出版由欧盟地平线欧洲研究创新计划的 Marie Sk?odowska-Curie COFUND 博士后计划协议(编号 101081355–SMASH)共同资助,并由斯洛文尼亚共和国和欧盟通过欧洲区域发展基金资助。由欧盟共同资助。观点

Bojan Nikolic | Marko Djukanovic
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号