Abundancy of $z$-Šoltés' digraphs

基本信息

• 论文ID: 2501.00102
• 标题: Abundancy of $z$-Šoltés' digraphs
• 作者: Stijn Cambie (KU Leuven Campus Kulak-Kortrijk)
• 分类: math.CO (组合数学)
• 提交时间: 2024年12月30日
• 论文链接: https://arxiv.org/abs/2501.00102

摘要

本文证明了无穷多个Šoltés有向图的存在性，这是Šoltés图的有向图类似物。同时给出了一个具有平凡自同构群的Šoltés有向图的例子。

研究背景与动机

问题背景

1. Šoltés图的定义: 源于Šoltés在1991年的论文，Šoltés图是指移除任意顶点后总距离恰好减少某个固定值的图。
2. 有向图推广: 本文将这一概念推广到有向图，定义$z$-Šoltés有向图为移除任意顶点后总距离减少恰好$z$的有向图。
3. 特殊情况: 当$z=0$时称为Šoltés有向图；当$z≤0$时称为负Šoltés有向图。

研究动机

1. 理论完善: 回答文献5, Question 13中关于是否存在无穷多个最小度至少为3的负Šoltés图的问题。
2. 有向图视角: 通过在有向图情况下确认这一猜想来加强对原问题的理解。
3. 丰富性证明: 证明不仅存在无穷多个负Šoltés有向图，还存在无穷多个Šoltés有向图。

核心贡献

1. 主要定理: 证明了对于每个整数$z$，都存在无穷多个有向图$D$使得对任意顶点$v$都有$W(D) - W(D \setminus v) = z$。
2. Šoltés有向图的无穷性: 作为主要定理的推论，证明了存在无穷多个Šoltés有向图。
3. 具体构造: 给出了具体的Šoltés有向图例子，包括$D(11,\{1\}) \cong C_{11}$和$D(85,\{4\})$。
4. 非顶点传递例子: 构造了一个阶为3306、具有平凡自同构群的Šoltés有向图，这强烈反驳了相关猜想的有向图类似物。

方法详解

核心定义

定义4: 对于子集$S \subseteq [n-2] = \{1,2,\ldots,n-2\}$，定义循环有向图$D(n,S)$的顶点集为$V = [n]$，有向边集为： $E = \{(i, i-1) | i \in [n]\} \cup \{(i, i+k) | i \in [n], k \in S\}$ 其中数字按模$n$解释。

构造策略

1. 密集有向图的正值情况: 通过命题5证明，当$\delta^-(D) + \delta^+(D) \geq n \geq 4$时，有$W(D) - W(D \setminus v) > 0$。
2. 稀疏有向图的负值情况: 命题6证明，当$\max S \leq \frac{1}{9}n^{1/2}$且$n$足够大时，有$W(D_{n,S}) - W(D_{n,S} \setminus v) < 0$。

主要证明思路

证明分为三个关键步骤：

步骤1 (Claim 7): 选择$n \sim 6m^2$使得$D(n,[m])$满足$z-9m \leq W(D) - W(D-v) \leq z-3$。

步骤2 (Claim 8): 通过移除$[m]$中的一些大元素，构造$D(n,[m-\ell] \cup \{m-1,m\})$使得差值在$z$附近且为偶数。

步骤3: 通过精确移除适当数量的奇数元素，最终得到$W(D) - W(D \setminus v) = z$。

实验设置

具体例子验证

1. 小规模例子: $D(11,\{1\}) \cong C_{11}$和$D(85,\{4\})$都是Šoltés有向图。
2. 大规模构造: 构造了阶为3306的非顶点传递Šoltés有向图，具有平凡自同构群。

计算验证

对于$D(85,\{4\})$，验证移除顶点$v$后，其左邻居到右邻居的距离从2变为22，体现了距离的重新分布。

实验结果

主要结果

1. 定理1的证明: 成功构造了对于任意整数$z$都存在无穷多个$z$-Šoltés有向图。
2. 具体例子:
   • $D(85,\{4\})$是一个具体的Šoltés有向图
   • 构造了阶为960的2-正则、二部但非顶点传递的Šoltés有向图
   • 构造了阶为3306、具有平凡自同构群的Šoltés有向图

技术细节验证

在附录B中详细计算了参数选择的具体数值：

• 当$a = 6m-1$, $r = m$时：$W(D-v) - W(D) = \frac{7}{2}m^2 - O(m) > z$
• 当$a = 6m-1$, $r = 0$时：$W(D-v) - W(D) = -\frac{5}{2}m^2 - O(m) < z - 9m$

相关工作

历史发展

1. Šoltés原始工作: 1991年Šoltés首次提出相关概念
2. 图论中的应用: Wiener指数（总距离）的相关研究
3. 顶点传递图: Adam猜想的有向图类似物及其反例

本文贡献的定位

本文将图论中的Šoltés性质推广到有向图，并通过循环有向图的构造方法给出了系统的存在性证明。

结论与讨论

主要结论

1. 对于任意整数$z$，都存在无穷多个$z$-Šoltés有向图
2. 特别地，存在无穷多个Šoltés有向图（$z=0$情况）
3. 存在具有平凡自同构群的Šoltés有向图，强烈反驳了相关猜想

理论意义

这些发现加强了文献5中关于图情况的直觉，即问题的本质在于负Šoltés图无穷存在性的极值问题。如果存在明显丰富的负Šoltés图，我们可以期望Šoltés图也很丰富。

未来方向

1. 研究非同构的$z$-Šoltés有向图的精确计数
2. 探索其他图类中的类似性质
3. 研究Šoltés性质与其他图论参数的关系

深度评价

优点

1. 理论完整性: 系统地解决了Šoltés图在有向图中的推广问题
2. 构造方法创新: 通过循环有向图的巧妙构造实现了参数的精确控制
3. 反例的强度: 构造的具有平凡自同构群的例子是对相关猜想的强烈反驳
4. 计算严谨性: 附录中的详细计算保证了结果的可靠性

技术亮点

1. 分步构造策略: 将复杂的存在性证明分解为三个可控的步骤
2. 参数优化: 通过$n \sim 6m^2$的选择实现了最优的参数平衡
3. 奇偶性控制: 巧妙利用奇数元素的移除来实现精确的差值调节

局限性

1. 构造的复杂性: 虽然证明了存在性，但具体构造过程相当复杂
2. 计数问题: 对于非同构图的精确计数仍然困难
3. 应用范围: 主要是理论结果，实际应用价值有限

影响力评估

1. 理论贡献: 为组合图论中的Šoltés问题提供了完整的有向图解答
2. 方法论价值: 循环有向图的构造方法可能适用于其他类似问题
3. 反驳价值: 对相关猜想的反驳具有重要的理论意义

参考文献

论文引用了10篇主要文献，涵盖了Šoltés图的原始工作、Wiener指数研究、循环图论以及相关的组合优化问题，体现了研究的系统性和完整性。