2025-11-23T03:37:16.288381

Moving through Cartesian products, coronas and joins in general position

Klavžar, Krishnakumar, Kuziak et al.
The general position problem asks for large sets of vertices such that no three vertices of the set lie on a common shortest path. Recently a dynamic version of this problem was defined, called the \emph{mobile general position problem}, in which a collection of robots must visit all the vertices of the graph whilst remaining in general position. In this paper we investigate this problem in the context of Cartesian products, corona products and joins, giving upper and lower bounds for general graphs and exact values for families including grids, cylinders, Hamming graphs and prisms of trees.
academic

Moving through Cartesian products, coronas and joins in general position

基本信息

  • 论文ID: 2505.00535
  • 标题: Moving through Cartesian products, coronas and joins in general position
  • 作者: Sandi Klavžar, Aditi Krishnakumar, Dorota Kuziak, Ethan Shallcross, James Tuite, Ismael G. Yero
  • 分类: math.CO (组合数学)
  • 发表时间: 2025年10月16日 (arXiv版本)
  • 论文链接: https://arxiv.org/abs/2505.00535

摘要

一般位置问题要求找到大的顶点集合，使得集合中没有三个顶点位于同一条最短路径上。最近定义了该问题的动态版本，称为移动一般位置问题，其中一组机器人必须访问图的所有顶点，同时保持一般位置。本文在笛卡尔积、冠积和连接的背景下研究这个问题，给出一般图的上下界以及包括网格、柱面、汉明图和树的棱镜等图族的精确值。

研究背景与动机

问题起源

  1. 静态一般位置问题：起源于Dudeney的几何难题，要求在图中找到最大的顶点集合，使得集合中任意三个顶点都不位于同一条最短路径上
  2. 机器人通信应用：假设机器人通过最短路径发送信号进行通信，为避免通信被干扰，需要确保没有机器人位于其他两个机器人之间的最短路径上
  3. 动态需求：现实世界中的机器人导航是动态的，需要在网络中移动，这促使研究者考虑移动版本的一般位置问题

研究意义

  1. 理论价值：扩展了传统图论中一般位置问题的研究范围，从静态扩展到动态
  2. 实际应用：为移动机器人的路径规划和协调提供理论基础
  3. 图结构分析：通过研究不同图积运算下的移动一般位置数，深化对图结构的理解

核心贡献

  1. 建立基础理论框架：为笛卡尔积、冠积和连接图的移动一般位置数提供了系统的上下界
  2. 精确值计算：给出了多个重要图族的移动一般位置数的精确公式，包括：
    • 完全图的笛卡尔积：Mobgp(Kn□Km)\text{Mobgp}(K_n \square K_m)
    • 网格图：Mobgp(Pn□Pm)=3\text{Mobgp}(P_n \square P_m) = 3 (当n,m≥3n,m \geq 3时)
    • 树的棱镜：Mobgp(T□K2)=ℓ(T)\text{Mobgp}(T \square K_2) = \ell(T) (叶子数)
    • 柱面图和环面图的部分结果
  3. 界的紧致性分析：证明了所提出界的紧致性，并给出了达到界的具体图族
  4. 算法构造：为多个图族构造了具体的移动一般位置集合和移动序列

方法详解

任务定义

一般位置集：图GG的顶点子集SS称为一般位置集，如果SS中没有三个顶点位于GG的同一条最短路径上。

移动一般位置集：如果从一般位置集SS开始，存在一系列合法移动使得图的每个顶点至少被某个机器人访问一次，则SS称为移动一般位置集。

合法移动：机器人从顶点uu移动到相邻顶点vv的移动u⇝vu \rightsquigarrow v是合法的，当且仅当：

  1. vv当前没有机器人
  2. 移动后的新配置仍然是一般位置集

移动一般位置数：Mobgp(G)\text{Mobgp}(G)表示图GG的最大移动一般位置集的大小。

核心技术方法

1. 笛卡尔积的界分析

对于笛卡尔积G□HG \square H，论文建立了两个重要的下界：

命题2.1：

  • Mobgp(G□H)≥max⁡{Mobgp(G),Mobgp(H)}\text{Mobgp}(G \square H) \geq \max\{\text{Mobgp}(G), \text{Mobgp}(H)\}
  • Mobgp(G□H)≥max⁡{gpo(G),gpo(H)}\text{Mobgp}(G \square H) \geq \max\{\text{gp}^o(G), \text{gp}^o(H)\}

其中gpo(G)\text{gp}^o(G)是外一般位置数。

2. 层分析技术

利用笛卡尔积的层结构（GG-层和HH-层）进行分析：

  • GG-层：由V(G)×{h}V(G) \times \{h\}诱导的子图，记为GhG^h
  • HH-层：由{g}×V(H)\{g\} \times V(H)诱导的子图，记为gH{}^gH

3. 凸性利用

关键观察：笛卡尔积中的层是凸子图，这意味着层内的最短路径不会离开该层。

4. 构造性证明方法

对于下界证明，论文采用构造性方法：

  1. 在特定层中放置机器人
  2. 设计具体的移动序列
  3. 验证每步移动的合法性
  4. 证明所有顶点都能被访问

技术创新点

  1. 层间移动策略：开发了在不同层之间安全移动机器人的技术，保持一般位置性质
  2. 对称性利用：巧妙利用图的对称性简化移动序列的设计
  3. 组合几何洞察：将移动一般位置问题与组合几何中的位置问题联系起来
  4. 递归构造：对于某些图族，建立了递归的构造方法

实验设置

理论验证方法

作为纯数学论文，本文采用严格的数学证明而非实验验证：

  1. 构造性证明：通过显式构造移动一般位置集合证明下界
  2. 反证法：通过假设存在更大的集合导出矛盾来证明上界
  3. 归纳法：对某些参数化的图族使用数学归纳法
  4. 计算机辅助验证：对于复杂情况（如环面图），使用计算机搜索验证结果

分析的图族

  1. 完全图的笛卡尔积：Kr□KsK_r \square K_s
  2. 路径的笛卡尔积：Pn□PmP_n \square P_m（网格图）
  3. 树的棱镜：T□K2T \square K_2
  4. 柱面图：Cr□PsC_r \square P_s
  5. 环面图：Cr□CsC_r \square C_s
  6. 冠积：G⊙HG \odot H
  7. 连接：G∨HG \vee H

实验结果

主要理论结果

1. 完全图笛卡尔积的精确值

定理2.4：对于n≥m≥1n \geq m \geq 1：

n & \text{if } m \in \{1,2\} \\ n + m - 3 & \text{if } m \geq 3 \end{cases}$$ #### 2. 网格图的结果 **定理3.2**：对于$n,m \geq 3$，$\text{Mobgp}(P_n \square P_m) = 3$ **定理3.3**：对于无限网格，$\text{Mobgp}(P_\infty \square P_\infty) = 4$ #### 3. 树的棱镜 **定理3.1**：对于任意阶数至少为3的树$T$，$\text{Mobgp}(T \square K_2) = \ell(T)$ 其中$\ell(T)$表示树$T$的叶子数。 #### 4. 柱面图的部分结果 **定理3.4**：对于$n \geq 3$： $$\text{Mobgp}(C_n \square K_2) = \begin{cases} 3 & \text{if } n = 3 \\ 2 & \text{if } n = 4 \\ 4 & \text{otherwise} \end{cases}$$ #### 5. 冠积的界 **定理4.1**：对于任意图$G$和$H$： $$\max\{\text{Mobgp}(G), \text{Mobgp}(H \vee K_1)\} \leq \text{Mobgp}(G \odot H) \leq \max\{n(G), \text{gp}(H \vee K_1)\}$$ #### 6. 连接图的界 **定理4.4**：如果$G$和$H$的团数至少为2且不都是团，则： $$\min\{\omega(G), \omega(H)\} + 1 \leq \text{Mobgp}(G \vee H) \leq \omega(G) + \omega(H) - 1$$ ### 界的紧致性 论文证明了所有提出的界都是紧致的，通过具体的图族达到这些界： 1. **下界紧致性**：通过$K_r \square P_s$证明命题2.1中的界是紧致的 2. **上界紧致性**：通过星图的笛卡尔积等例子证明上界的紧致性 3. **差距分析**：证明了移动一般位置数与一般位置数之间的差距可以任意大 ### 重要发现 1. **移动性的代价**：移动一般位置数通常严格小于一般位置数 2. **结构依赖性**：移动一般位置数强烈依赖于图的结构特性 3. **积运算的影响**：不同的图积运算对移动一般位置数有不同的影响模式 ## 相关工作 ### 静态一般位置问题 1. **起源**：Dudeney的几何问题，后由Manuel和Klavžar引入图论 2. **笛卡尔积研究**：大量文献研究笛卡尔积中的一般位置集 3. **变种问题**：外一般位置、下一般位置、互可见性等相关概念 ### 移动版本问题 1. **首次提出**：Klavžar等人在2023年首次定义移动一般位置问题 2. **特殊图族**：已研究的图族包括块图、根积、Kneser图、单圈图等 3. **相关动态问题**：移动互可见性问题等 ### 机器人导航应用 1. **互可见性问题**：在机器人导航和通信中的应用 2. **路径规划**：与机器人路径规划中的避障问题相关 3. **分布式算法**：与分布式机器人系统中的协调问题相关 ## 结论与讨论 ### 主要结论 1. **系统性框架**：建立了笛卡尔积、冠积和连接图的移动一般位置数的系统性理论框架 2. **精确结果**：获得了多个重要图族的移动一般位置数的精确值 3. **界的完整性**：提供了紧致的上下界，并证明了它们的最优性 4. **构造方法**：开发了构造移动一般位置集合的一般方法 ### 局限性 1. **计算复杂性**：论文没有讨论计算移动一般位置数的算法复杂性 2. **一般图**：对于一般图的移动一般位置数仍缺乏有效的计算方法 3. **动态策略**：移动策略的优化问题没有深入研究 4. **实际约束**：没有考虑实际机器人系统中的物理约束 ### 未来方向 论文在第5节提出了多个开放问题： 1. **笛卡尔积的非平凡上界**：寻找$\text{Mobgp}(G \square H)$的更好上界 2. **高维情况**：研究$k$重笛卡尔积$P_\infty^{\square k}$的移动一般位置数 3. **特殊图族**：确定柱面图$C_7 \square P_s$和$C_{10} \square P_s$的精确值 4. **其他图积**：研究强积和直积的移动一般位置问题 5. **超立方体**：确定超立方体的移动一般位置数 ## 深度评价 ### 优点 1. **理论深度**：提供了移动一般位置问题的深入理论分析，建立了系统性的理论框架 2. **方法创新**：开发了多种分析技术，包括层分析、对称性利用和构造性证明方法 3. **结果完整性**：不仅给出了界，还证明了界的紧致性，并提供了达到界的具体例子 4. **写作清晰**：论文结构清晰，证明严谨，易于理解和验证 5. **问题重要性**：研究的问题具有重要的理论价值和潜在的实际应用价值 ### 不足 1. **算法方面**：缺乏有效的算法来计算一般图的移动一般位置数 2. **复杂性分析**：没有讨论相关问题的计算复杂性 3. **实际应用**：与实际机器人系统的联系还需要进一步加强 4. **开放问题**：仍有许多重要的开放问题有待解决 ### 影响力 1. **理论贡献**：为组合数学和图论领域贡献了新的研究方向 2. **方法论价值**：提供的分析方法可以应用于其他相关问题 3. **应用潜力**：为机器人路径规划和网络优化提供了理论基础 4. **研究启发**：提出的开放问题将激发后续研究 ### 适用场景 1. **机器人网络**：多机器人系统的协调和路径规划 2. **传感器网络**：传感器节点的部署和通信优化 3. **网络安全**：分布式系统中的安全通信协议设计 4. **图论研究**：作为图论中位置问题研究的理论基础 ## 参考文献 论文引用了32篇相关文献，主要包括： 1. **一般位置问题的奠基工作**：Manuel & Klavžar (2018) 2. **笛卡尔积中一般位置的系列研究**：Klavžar等人的多篇论文 3. **机器人导航相关工作**：Aljohani, Sharma等人的应用研究 4. **移动一般位置问题的首篇论文**：Klavžar等人 (2023) --- 本论文为移动一般位置问题提供了系统性的理论分析，在组合数学和图论领域具有重要的理论价值，同时为实际的机器人导航应用提供了理论基础。虽然仍有一些开放问题有待解决，但论文建立的理论框架和分析方法为后续研究奠定了坚实的基础。