2025-11-17T15:31:13.202496

Remoteness, order, size and connectivity constraints in digraphs

Mallu
Let \( D \) be a strongly connected digraph. The average distance of a vertex \( v \) in \( D \) is defined as the arithmetic mean of the distances from \( v \) to all other vertices in \( D \). The remoteness \( ρ(D) \) of \( D \) is the maximum of the average distances of the vertices in \( D \). In this paper, we provide a sharp upper bound on the remoteness of a strong digraph with given order, size, and vertex-connectivity. We then characterise the extremal digraphs that maximise remoteness among all strong digraphs of order \(n\), size at least \(m\), and vertex-connectivity \(κ\). Finally, we demonstrate that the upper bounds on the remoteness of a graph given its order, size, and connectivity constraints (see \cite{DanMafMal2025}) can be extended to a larger class of digraphs containing all graphs, the Eulerian digraphs.
academic

Remoteness, order, size and connectivity constraints in digraphs

基本信息

  • 论文ID: 2510.08841
  • 标题: Remoteness, order, size and connectivity constraints in digraphs
  • 作者: Sufiyan Mallu (University of Johannesburg, South Africa)
  • 分类: math.CO (组合数学)
  • 发表时间: October 13, 2025 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.08841

摘要

本文研究强连通有向图的远程性(remoteness)问题。对于强连通有向图 DD，顶点 vv 的平均距离定义为从 vv 到所有其他顶点的距离的算术平均值，而 DD 的远程性 ρ(D)\rho(D) 定义为所有顶点平均距离的最大值。论文提供了给定阶数、大小和顶点连通性的强有向图远程性的紧上界，刻画了在所有阶数为 nn、大小至少为 mm、顶点连通性为 κ\kappa 的强有向图中使远程性最大的极值有向图，并证明了无向图关于阶数、大小和连通性约束的远程性上界可以推广到包含所有图的更大类有向图——欧拉有向图。

研究背景与动机

  1. 研究问题：虽然图中的距离问题已被广泛研究，但有向图中距离的研究相对不足，特别是邻近性(proximity)和远程性概念在有向图中的探索还不够深入。
  2. 问题重要性：
    • 距离参数在图论中具有基础性地位，对网络分析、算法设计等领域有重要应用
    • 有向图更能准确建模现实世界中的非对称关系，如交通网络、社交网络等
    • 连通性约束下的极值问题具有重要的理论价值
  3. 现有方法局限性：
    • Ai等人1首次将邻近性和远程性概念扩展到有向图，但相关研究仍然有限
    • 现有结果主要集中在仅考虑阶数约束的情况，缺乏同时考虑大小和连通性的结果
  4. 研究动机：本文旨在填补有向图远程性理论的空白，建立更精确的界限和刻画极值结构。

核心贡献

  1. 建立了新的上界：给出了 κ\kappa-连通强有向图在给定阶数、大小和顶点连通性下远程性的紧上界
  2. 刻画了极值结构：完全刻画了达到远程性上界的极值有向图——κ\kappa-连通路径完全有向图
  3. 推广了已有结果：证明了无向图的远程性上界可以推广到欧拉有向图这一更大的图类
  4. 提供了构造性证明：通过具体构造极值图族，证明了所得界限的紧性

方法详解

任务定义

输入：强连通有向图 DD 及其参数（阶数 nn、大小 mm、顶点连通性 κ\kappa） 输出：远程性 ρ(D)\rho(D) 的上界 约束条件：DD 必须是 κ\kappa-连通的强有向图

核心概念

  1. 平均距离：顶点 vv 的平均距离定义为 σ(v,D)=1n−1∑w∈V(D)dD(v,w)\sigma(v,D) = \frac{1}{n-1}\sum_{w \in V(D)} d_D(v,w)
  2. 远程性：有向图的远程性定义为 ρ(D)=max⁡v∈V(D)σ(v,D)\rho(D) = \max_{v \in V(D)} \sigma(v,D)
  3. κ\kappa-连通路径完全有向图：形如 K1+←[Kκ↔]ℓ+←Ka↔+←Kb↔K_1 \overleftarrow{+} [\overleftrightarrow{K_\kappa}]^\ell \overleftarrow{+} \overleftrightarrow{K_a} \overleftarrow{+} \overleftrightarrow{K_b} 的有向图，其中 a≥κa \geq \kappa。

主要技术方法

  1. 极值分析：通过分析使远程性最大的顶点的距离分布，建立结构约束
  2. 归纳构造：逐步证明极值图必须具有特定的路径完全结构
  3. 尺寸优化：在固定远程性的前提下，分析图的最大尺寸约束

关键引理

引理 3.1：

  • (a) 对于 κ\kappa-连通路径完全有向图 HH，添加任何弧都会减少其远程性
  • (b) 两个不同的 κ\kappa-连通路径完全强有向图之间存在严格的大小-远程性权衡关系
  • (c) 给定 n,κn, \kappa，存在特定大小的 κ\kappa-连通路径完全强有向图的充要条件

实验设置

本文为纯理论研究，不涉及实验验证，而是通过严格的数学证明来验证结果的正确性。

证明策略

  1. 存在性证明：构造具体的极值图族
  2. 唯一性证明：证明极值图的结构唯一性
  3. 紧性验证：通过具体例子验证界限的紧性

主要结果

核心定理

定理 3.2：设 DD 是阶数为 nn、大小为 mm 的 κ\kappa-连通强有向图，其中 m≤n2−2n−1m \leq n^2 - 2n - 1，则 ρ(D)≤ρ(DPKn,m,κ)\rho(D) \leq \rho(DPK_{n,m,\kappa})

当 m≡(n2−2n−1)(modκ)m \equiv (n^2-2n-1) \pmod{\kappa} 且满足特定条件时，等号成立当且仅当 D=DPKn,m,κD = DPK_{n,m,\kappa}。

具体界限

推论 3.3：在适当条件下， ρ(D)≤nκ+2−1κ−κ−1n−1−m∗κ(n−1)\rho(D) \leq \frac{n}{\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m^*}{\kappa(n-1)}

其中 m∗m^* 是满足 m∗≥mm^* \geq m 且 m∗≡(n2−2n−1)(modκ)m^* \equiv (n^2-2n-1) \pmod{\kappa} 的最小整数。

欧拉有向图的结果

定理 4.3：设 DD 是阶数为 nn、大小至少为 2m02m_0 的 κ\kappa-连通欧拉有向图，则 ρ(D)≤n2κ+2−1κ−κ−1n−1−m0κ(n−1)\rho(D) \leq \frac{n}{2\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m_0}{\kappa(n-1)}

技术创新点

  1. 结构刻画的完整性：不仅给出了上界，还完全刻画了达到上界的极值结构
  2. 多参数约束的处理：同时考虑阶数、大小和连通性三个参数的约束
  3. 从无向图到有向图的推广：巧妙地利用欧拉有向图的性质，将无向图的结果推广到有向图
  4. 模运算条件的引入：发现了大小参数必须满足的模运算条件

相关工作

历史发展

  1. Zelinka 29 和 Aouchiche, Hansen 4：建立了连通图远程性的基本上界 ρ(G)≤n/2\rho(G) \leq n/2
  2. Ai等人 1：将远程性概念推广到有向图
  3. Entringer等人 18：考虑了图的大小约束
  4. Dankelmann等人 15：建立了带连通性约束的无向图远程性界限

本文贡献的定位

本文是第二篇专门研究有向图远程性的论文，填补了有向图理论中的重要空白，并成功地将无向图的精确结果推广到了更广泛的有向图类。

结论与讨论

主要结论

  1. 建立了 κ\kappa-连通强有向图远程性的紧上界
  2. 完全刻画了极值图的结构（κ\kappa-连通路径完全有向图）
  3. 证明了无向图的远程性界限可以推广到欧拉有向图

理论意义

  • 丰富了有向图的距离理论
  • 为网络分析提供了新的理论工具
  • 建立了无向图和有向图理论之间的桥梁

未来方向

  1. 研究更一般的有向图类的远程性
  2. 探索远程性与其他图参数的关系
  3. 考虑加权有向图的情况

深度评价

优点

  1. 理论完整性：不仅给出界限，还完全刻画了极值结构
  2. 技术深度：证明技巧精巧，特别是在处理有向图的复杂性方面
  3. 结果的紧性：所有主要结果都是紧的，说明界限是最优的
  4. 推广的巧妙性：通过欧拉有向图将无向图结果推广到有向图的方法很有创意

不足

  1. 应用范围：主要是理论结果，实际应用价值需要进一步探索
  2. 计算复杂性：没有讨论相关问题的计算复杂性
  3. 参数范围：某些结果需要满足特定的模运算条件，限制了适用范围

影响力

  1. 理论贡献：为有向图距离理论奠定了重要基础
  2. 方法论价值：证明技巧可能适用于其他有向图问题
  3. 后续研究：为进一步研究有向图的其他距离参数提供了框架

适用场景

  1. 网络分析中的中心性度量
  2. 有向图的结构分析
  3. 极值图论研究
  4. 算法设计中的理论界限分析

参考文献

论文引用了29篇相关文献，涵盖了图论中距离问题的主要研究成果，特别是：

  • 1 Ai等人关于有向图邻近性和远程性的开创性工作
  • 15 Dankelmann等人关于无向图远程性的最新结果
  • 29 Zelinka关于远程性的早期工作

总体评价：这是一篇高质量的理论论文，在有向图远程性这一重要但相对较新的研究领域做出了实质性贡献。论文的技术水平较高，结果完整且紧致，为该领域的后续研究奠定了坚实基础。