关于给定阶数和最大度数的树的最大σ-不规则性

《Discrete Applied Mathematics》：On the maximum σ-irregularity of trees with given order and maximum degree

　　

# 摘要

图的σ-不规则度指标定义为所有边上度数差的平方和，提供了一种衡量结构异质性的敏感指标。本文研究了在阶为n且最大度为Δ≥4的所有树中最大化σ(T)的问题。通过将问题表示为边-度数重数形式，我们推导出了一个线性规划模型并分析了其对偶问题。这种方法得出了σ(T)的精确上界，并导致了极值度数-对分布的详细描述。我们证明，当n≡1(modΔ)和n≡0(modΔ)时，极值问题可以完全解决。当n≡1(modΔ)时，线性规划存在整数最优解，且σ(T)的上界是紧的。当n≡0(modΔ)时，线性松弛不能被任何树达到；尽管如此，通过引入由对偶松弛变量导出的惩罚函数，我们确定了σ(T)的精确最大值。在两种情况下，所有极值树都被显式刻画，且仅由度数为1、2和Δ的顶点组成，其中与Δ度顶点关联的边起着主导作用。

# 引言

如果一个图的所有顶点的度数不全相等，则称该图为不规则图。量化图偏离规则性的程度在理论和应用图论中一直备受关注。度量度数异质性的最早定量指标之一是Snijders[12]提出的度方差。随后，Albertson[3]引入了现在经典的不规则度指标irr(G)=∑_{uv∈E(G)}|d_G(u)?d_G(v)|，它衡量相邻顶点间的度数不平衡总量。这一不变量通常被称为Albertson不规则度，已被广泛研究；参见[1]、[3]、[9]及其中所列参考文献。

基于度数的不规则度量在应用中已证明特别有用。在网络科学中，它们作为通信网络和社会网络中结构异质性的指标[6]。在数学化学中，此类指标被用作定量构效关系和构活性关系(QSPR/QSAR)中的分子描述符，用于捕捉局部键合环境的变化[7]、[11]。这些应用促使人们引入了对大局部度数差异更敏感的其他不规则度指标。

在这些变体中，σ-不规则度指标（或简称σ-指标）发挥了突出作用，对于图G=(V,E)定义为σ(G)=∑_{uv∈E(G)}(d_G(u)?d_G(v))^2。该指标可视为Albertson不规则度的二次类比。通过对度数差取平方，σ(G)对连接高度不均匀度数顶点的边赋予更大权重，使其成为结构不平衡的特别敏感度量。σ-指标在[2]中得到系统研究，其中刻画了在所有固定阶图中最大化σ(G)的极值图。进一步的基元性质，包括σ-指标逆问题的解，在[8]中获得。与其他不规则度量的比较及其应用见[10]，而Arif等人[4]研究了以两个主要特征值刻画的图族的σ(G)及相关指标，并将所得值应用于QSPR分析。

一个自然且活跃的研究方向是在附加结构约束下σ(G)的极值问题。一旦已知固定阶图的极值图，自然而然会问：当可允许图类受到限制时问题表现如何？最重要的限制之一就是树类，它在数学上既是基本的又在应用中高度相关。在化学图论中，树模拟无环分子结构；在此背景下，当顶点度受限于4时，人们常说化学树。化学树的σ-不规则度在[13]中得到研究，其中获得了所有固定阶化学树中σ最大的树的完全刻画。

最近，Dimitrov等人[5]对σ-极值树在给定最大度Δ=5下的情况开始了系统研究。他们建立了σ-最大树的一般结构性质，适用于任意Δ≥3，并对Δ=5的情形进行了详细分析。在该设定下，他们证明每个具有n个顶点且在Δ(G)=5条件下最大化σ(G)的树仅包含度数为1、2和5的顶点。此外，此类极值树中几乎所有边连接叶子与度为5的顶点，或连接度为5的顶点与度为2的顶点，而两个度为5的顶点之间或两个度为2的顶点之间的边仅例外出现。这些发现支持了一种一般启发式方法：对于固定的最大度Δ，具有大σ-不规则度的树往往表现出强极化的度数分布，即拥有许多度为Δ的顶点和许多叶子，而度为2的顶点以相当数量出现并主要作为两个极端之间的连接器。

本文考虑阶为n且最大度为Δ≥4的树。我们设定此条件主要是出于表述清晰度。虽然我们的线性规划框架对Δ∈{2,3}完全有效，但这些情形缺乏结构丰富性。对于Δ=2，唯一的树是路径，使得优化变得平凡，因为线性规划自然产生精确的整数解。对于Δ=3，2和3之间缺乏中间度数会导致我们在分析中产生空的指标区间。因此，设定Δ≥4简化了证明并避免了特殊情况警告，使我们能够专注于中间度数分析和分支现象的完整复杂性。该问题在完全一般形式下似乎很困难，因为极值结构敏感地依赖于n与Δ之间的算术关系。为解决此问题，我们将极值问题重新表述为关于边-度数重数的线性优化问题，并分析其对偶。这得出了σ(T)的精确上界，并允许显式推导极值树。

我们的主要结果表明，极值问题可以对同余类n≡1(modΔ)和n≡0(modΔ)完全解决。当n≡1(modΔ)时，线性规划存在整数最优解，所得到的σ(T)上界是紧的并由唯一的极值度数-对配置达到。当n≡0(modΔ)时，线性松弛不能被任何树达到。尽管如此，通过引入由对偶松弛变量导出的适当惩罚函数，我们确定了σ(T)的精确最大值，并在此情形下获得了所有极值树的完全结构刻画。在我们处理的这两个同余类中，极值树仅由度数为1、2和Δ的顶点组成，类型为(1,Δ)和(2,Δ)的边起着主导作用。初步证据，由对更大Δ值的穷举计算机搜索支持，表明随着Δ增加，可能出现涉及额外中间度数的新极值配置，这反映了当n模Δ的余数远离0和1时最小惩罚值的逐渐增加。

本文组织如下。在第2节中我们引入符号并为给定阶和最大度的树上最大化σ(T)推导出线性规划模型。在第3节中我们求解相应的线性规划并确定最优度数及边度数-对分布，讨论整数性和关于n的同余条件的角色。在第4节中我们引入惩罚函数并分析n≡0(modΔ)的情形，建立精确上界和唯一性结果。最后，在第4.1节中我们为两个同余类n≡1(modΔ)和n≡0(modΔ)提供所有极值树的显式构造，从而以具体的组合实现补充抽象的优化结果。

# 问题线性规划模型的建立

设T是n个顶点且最大度为Δ的树。对于1≤i≤Δ，记n_i为度为i的顶点数，对于1≤i≤j≤Δ，记m_{i,j}为连接度为i的顶点与度为j的顶点的边数。因此，∑_{1≤i≤j≤Δ} m_{i,j} = |E(T)| = n?1，而量m_{i,j}捕捉了T的完整度数-对结构。

**定义2.1** 对于边集为E(G)的连通图G，sigma-不规则度指标定义为σ(G) = ∑_{uv∈E(G)}(d_G(u)?d_G(v))^2。

使用上述引入的边-重数变量m_{i,j}，

# 线性规划的求解

我们首先确定线性松弛的最优解，不对变量m_{i,j}施加整数条件。

**注3.1** 我们将使用以下线性规划中的标准事实。如果原始线性规划及其对偶问题都存在目标值相同的目标可行解，则两个解都是最优的（强对偶性）。此外，在最优原始-对偶对中，原始变量为正仅当相应的对偶约束是紧的（互补性）。

# 惩罚函数及n≡0(modΔ)的情形

当线性规划松弛不产生整数最优解时（例如当n≡0(modΔ)），为评估σ-不规则度的最大值，我们使用LP模型的约束导出精确的惩罚关系。

回忆定理3.2中的顶点-度数和边数恒等式：
∑_{1≤i≤j≤Δ} 1/(1/i+1/j) m_{i,j} = n
和
∑_{1≤i≤j≤Δ} m_{i,j} = n?1。

设λ和μ分别对应这两个约束的最优对偶变量，具体为：λ = 4Δ?6 和 μ = Δ^2?6Δ+3+6Δ。

将第一个恒等式乘以λ，

# 结论

本文研究了在固定阶n且给定最大度Δ≥4的树中最大化σ-不规则度指标的问题。通过将极值问题重新表述为关于边-度数重数的线性优化问题并利用其对偶，我们得出了σ(T)的精确上界，并在n≡1(modΔ)和n≡0(modΔ)的情形下获得了所有极值树的显式结构刻画。在两个同余类中，极值树仅由

# 利益冲突声明

作者声明他们没有已知的可能影响本文所报告工作的竞争财务利益或个人关系。

# 致谢

本研究由塞尔维亚共和国教育、科学和技术发展部的研究项目支持（编号451-03-34/2026-03/200124）。

米兰·巴希奇