2025-11-17T18:31:12.470972

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

Babu, Brešar, S et al.
The concept of mutual-visibility (MV) has been extended in several directions. A vertex subset $S$ of a graph $G$ is a $k$-distance mutual-visibility ($k$DMV) set if for any two vertices in $S$, there is a geodesic between them of length at most $k$ whose internal vertices are not in $S$. In this paper, we combine this with the MV coloring as follows. For any integer $k\geq1$, a $k$DMV coloring of $G$ is a partition of $V(G)$ into $k$DMV sets, and the $k$DMV chromatic number $χ_{μ_k}(G)$ is the minimum cardinality of such a partition. When $k=1$ or $k\ge {\rm diam}(G)$, it equals the clique cover number $θ(G)$ or the MV chromatic number $χ_μ(G)$, respectively. So, our attention is given to $1<k<{\rm diam}(G)$ with $k=2$ producing the most interesting results. We prove that $χ_{μ_2}(G)\le|V(G)|/2$ and present large families of graphs that attain the bound. In addition, $χ_{μ_2}(G)$ is bounded from above by the total domination number $γ_t(G)$ if $G$ is isolate-free, while in graphs $G$ with girth $g(G)\geq7$, $χ_{μ_2}(G)$ is bounded from below by the domination number $γ(G)$. A surprising relation with the exact distance-2 graphs is found, which results in $θ(G^{[\natural2]})=γ_{t}(G)$ for any isolate-free graph $G$ with $g(G)\geq7$. The relation is explored further in lexicographic product graphs, where we prove the sharp inequalities $χ_{μ_{2}}(G\circ H)\leq θ(G^{[\natural2]})\leq θ\big{(}(G\circ H)^{[\natural2]}\big{)}$. We also prove a sharp lower (resp. upper) bound on $χ_{μ_2}$ (resp. $χ_{μ_k}$) for the Cartesian (resp. strong) product of two connected graphs and show that they are widely sharp. Finally, we characterize the block graphs $G$ with $χ_{μ_k}(G)=χ_μ(G)$, where $k={\rm diam}(G)-1$.
academic

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

基本信息

  • 论文ID: 2510.10284
  • 标题: Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products
  • 作者: Saneesh Babu, Boštjan Brešar, Aparna Lakshmanan S, Babak Samadi
  • 分类: math.CO (组合数学)
  • 发表时间: 2025年10月11日
  • 论文链接: https://arxiv.org/abs/2510.10284

摘要

本文研究了k-距离互可见性着色问题，这是对Di Stefano在2022年引入的互可见性概念的扩展。对于图G的顶点子集S，如果S中任意两个顶点之间存在长度至多为k的测地线，且其内部顶点不在S中，则称S为k-距离互可见性集(k-DMV集)。论文将此概念与互可见性着色相结合，定义了k-DMV着色数χ_μ_k(G)。研究发现当k=2时产生最有趣的结果，证明了χ_μ_2(G) ≤ |V(G)|/2，并建立了与支配数、全支配数以及精确距离图的深刻联系。

研究背景与动机

  1. 问题起源: 互可见性概念最初由Di Stefano在2022年提出，与经典的"三点不共线"问题和平面移动机器人重新定位问题相关。
  2. 研究动机:
    • 互可见性概念虽然新颖，但已获得广泛关注(在MathSciNet中已有超过20次引用)
    • 现有研究主要关注互可见性集的最大基数，缺乏对着色问题的系统研究
    • k-距离限制使得通信更加高效，具有实际应用价值
  3. 实际意义: 在计算机网络或社交网络中，具有互可见性性质的顶点可以表示需要高效、保密通信的实体，确保消息不经过其他实体传递。

核心贡献

  1. 引入新概念: 首次定义了k-距离互可见性着色数χ_μ_k(G)，统一了团覆盖数(k=1)和互可见性着色数(k≥diam(G))
  2. 建立基本界限:
    • 证明了χ_μ_2(G) ≤ ⌈|V(G)|/2⌉，并给出达到此界的图族
    • 对于无孤立点的图，χ_μ_2(G) ≤ γ_t(G)
    • 对于围长至少为7的图，χ_μ_2(G) ≥ γ(G)
  3. 发现与精确距离图的联系: 证明了对于无孤立点且围长至少为7的图G，有θ(G♮2) = γ_t(G)
  4. 图乘积的系统研究:
    • 字典序乘积: χ_μ_2(G∘H) ≤ θ(G♮2) ≤ θ((G∘H)♮2)
    • 强乘积: χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)
    • 笛卡尔乘积: χ_μ_2(G□H) ≥ max{χ_μ_2(G)ρ_2(H), χ_μ_2(H)ρ_2(G)}
  5. 特殊图类的刻画: 完全刻画了满足χ_μ_k(G) = χ_μ(G)(其中k = diam(G)-1)的块图

方法详解

任务定义

给定图G和正整数k，k-距离互可见性着色是将V(G)划分为若干k-DMV集的着色方案。其中k-DMV集M满足：对于M中任意两个顶点u,v，存在长度至多为k的u,v-测地线，其内部顶点不在M中。

输入: 图G = (V,E)，正整数k 输出: V(G)的一个划分{S_1, S_2, ..., S_t}，使得每个S_i都是k-DMV集 目标: 最小化划分的集合个数t

核心技术方法

1. 基础理论建立

观察1: 对于直径为d的图G，有单调性链： χ_μ(G) = χ_μ_d(G) ≤ χ_μ_(G) ≤ ... ≤ χ_μ_1(G) = θ(G)

观察2: 基本下界 χ_μ_k(G) ≥ ⌈|V(G)|/μ_k(G)⌉

2. k=2情况的深入分析

定理4: 对于任意连通图G，χ_μ_2(G) ≤ ⌈n/2⌉

证明思路: 通过对生成树的归纳构造，将树分解为可用两种颜色着色的结构。

定理5: 若G无孤立点，则χ_μ_2(G) ≤ γ_t(G)

证明方法: 构造性证明，利用全支配集D = {v_1,...,v_γ_t(G)}，定义D_i = N_G(v_i)\⋃_^{i-1}N_G(v_j)，证明每个D_i都是2DMV集。

3. 围长与支配数的关系

引理6: 若g(G) ≥ 7，则χ_μ_2(G)-着色中每个颜色类C都是某个顶点的闭邻域的子集。

定理7: 若g(G) ≥ 7，则χ_μ_2(G) ≥ γ(G)

技术创新点

  1. 统一框架: 将团覆盖、互可见性着色统一到k-DMV着色框架中
  2. 围长条件的精确刻画: 证明了围长7是保证χ_μ_2(G) ≥ γ(G)的最小值
  3. 精确距离图联系: 首次建立了2DMV着色与精确距离-2图的深刻联系
  4. 图乘积的系统分析: 对三种主要图乘积给出了紧致的上下界

实验设置

理论验证方法

本文主要采用理论证明方法，通过构造具体的图族来验证界限的紧致性：

  1. 路径和圈: 计算了P_n和C_n的精确χ_μ_k值
  2. 特殊图族: 构造了达到各种界限的图族
  3. 乘积图: 分析了P_n⊠K_m等具体乘积图的性质

关键实例分析

命题2:

  • 对于路径P_n: χ_μ_k(P_n) = ⌈n/2⌉
  • 对于圈C_n: χ_μ_k(C_n) = ⌈n/3⌉ (当n ≤ 3k时)，⌈n/2⌉ (否则)

命题12: 对于P_n⊠K_m (n≥4, m≥2, k∈{2,...,n-2})： χ_μ_k(P_n⊠K_m) = 2⌊n/(k+2)⌋ + correction_term

实验结果

主要理论结果

  1. 基本界限的紧致性:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉对所有图成立，且被路径、长圈等达到
    • χ_μ_2(G) ≤ γ_t(G)对无孤立点图成立，且可构造使差值任意大的图族
  2. 围长条件的最优性:
    • 构造了围长为6但γ(G) = 5 > χ_μ_2(G) = 3的反例
    • 证明了围长7是保证χ_μ_2(G) ≥ γ(G)的最小条件
  3. 图乘积结果的锐利性:
    • 强乘积界χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)被无穷图族达到
    • 笛卡尔乘积下界被环面图等达到

精确距离图的惊人联系

定理8: 若G无孤立点且g(G) ≥ 7，则θ(G♮2) = χ_i_μ_2(G) = γ_t(G)

这个结果建立了三个看似不相关的图参数之间的等式关系，具有重要的理论意义。

超立方体的特殊性质

命题16: 对于n-超立方体Q_n，χ_μ_2(Q_n) ≤ γ(Q_n)

猜想: χ_μ_2(Q_n) = γ(Q_n)对所有n成立

相关工作

  1. 互可见性研究: Di Stefano (2022)引入基本概念，Cera等人扩展到k-距离版本
  2. 互可见性着色: Klavžar等人(2025)首次研究互可见性着色问题
  3. 精确距离图: 1980年代引入，近年来重新受到关注
  4. 支配理论: 经典图论研究领域，与本文建立了新的联系

结论与讨论

主要结论

  1. k-距离互可见性着色为研究图的结构性质提供了新的视角
  2. k=2的情况展现了与支配理论和精确距离图的深刻联系
  3. 不同图乘积下的行为揭示了该参数的本质特征
  4. 围长条件在确定参数界限中起关键作用

局限性

  1. 主要结果集中在k=2的情况，对于一般k值的研究较少
  2. 某些界限的紧致性仅在特定图族中验证
  3. 计算复杂性问题未涉及

未来方向

论文提出了三个具体的开放问题：

问题1: 刻画满足χ_μ_2(G) = θ(G)的块图G

问题2: 对于连通图G,H，是否有χ_μ_2(G□H) ≥ max{χ_μ_2(G)γ(H), χ_μ_2(H)γ(G)}？

问题3: 是否χ_μ_2(Q_n) = γ(Q_n)对所有超立方体成立？

深度评价

优点

  1. 理论深度: 建立了多个图论分支之间的新联系，特别是与支配理论和精确距离图的关系
  2. 结果完整性: 提供了大量紧致的上下界，并构造了达到界限的图族
  3. 技术创新: 围长条件的精确刻画和图乘积的系统分析展现了高超的技巧
  4. 写作清晰: 定义明确，证明严谨，结构合理

不足

  1. 计算复杂性缺失: 未讨论χ_μ_k(G)的计算复杂性
  2. 应用局限: 虽然提到了网络通信应用，但缺乏具体的应用场景分析
  3. 算法设计: 缺乏高效的算法来计算或近似χ_μ_k(G)

影响力

  1. 理论贡献: 为图论研究开辟了新方向，预期会引发后续研究
  2. 技术价值: 证明技巧和构造方法对相关研究具有参考价值
  3. 跨领域潜力: 与支配理论的联系可能促进两个领域的交叉发展

适用场景

  1. 网络设计: 在需要保证通信路径私密性的网络中应用
  2. 图论研究: 作为研究图结构性质的新工具
  3. 组合优化: 为相关优化问题提供理论基础

参考文献

论文引用了18篇相关文献，主要包括：

  • Di Stefano (2022): 互可见性概念的原始文献
  • Cera等人: k-距离互可见性的扩展
  • Klavžar等人: 互可见性着色的首次研究
  • 经典图论教材和支配理论文献

总体评价: 这是一篇高质量的理论图论论文，在互可见性这一新兴研究方向上做出了重要贡献。论文不仅建立了完整的理论框架，还发现了与经典图论概念的深刻联系，为该领域的发展奠定了坚实基础。虽然在应用和算法方面还有待进一步研究，但其理论价值和创新性使其成为该领域的重要文献。