2025-11-16T18:28:12.845274

On open-separating dominating codes in graphs

Chakraborty, Wagler
Using dominating sets to separate vertices of graphs is a well-studied problem in the larger domain of identification problems. In such problems, the objective is to choose a suitable dominating set $C$ of a graph $G$ which is also separating in the sense that the neighbourhoods of any two distinct vertices of $G$ have distinct intersections with $C$. Such a dominating and separating set $C$ of a graph is often referred to as a code in the literature. Depending on the types of dominating and separating sets used, various problems arise under various names in the literature. In this paper, we introduce a new problem in the same realm of identification problems whereby the code, called open-separating dominating code, or OD-code for short, is a dominating set and uses open neighbourhoods for separating vertices. The paper studies the fundamental properties concerning the existence, hardness and minimality of OD-codes. Due to the emergence of a close and yet difficult to establish relation of the OD-code with another well-studied code in the literature called open (neighborhood)-locating dominating code (referred to as the open-separating total-dominating code and abbreviated as OTD-code in this paper), we compare the two codes on various graph families. Finally, we also provide an equivalent reformulation of the problem of finding OD-codes of a graph as a covering problem in a suitable hypergraph and discuss the polyhedra associated with OD-codes, again in relation to OTD-codes of some graph families already studied in this context.
academic

On open-separating dominating codes in graphs

基本信息

  • 论文ID: 2402.03015
  • 标题: On open-separating dominating codes in graphs
  • 作者: Dipayan Chakraborty, Annegret K. Wagler
  • 分类: math.CO (组合数学), cs.DM (离散数学)
  • 发表时间: 2024年2月5日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2402.03015

摘要

本文在图的识别问题领域中引入了一个新的问题——开邻域分离支配码(OD-code)。该问题要求选择一个既是支配集又具有分离性质的顶点子集，使得任意两个不同顶点的开邻域与该子集的交集都不相同。论文系统研究了OD-码的存在性、计算复杂性和最小性等基本性质，并与已有的开邻域定位支配码(OTD-code)进行了深入比较。此外，论文将OD-码问题重新表述为超图覆盖问题，并讨论了相关的多面体结构。

研究背景与动机

问题背景

  1. 识别问题的重要性: 在图论中，使用支配集分离顶点是识别问题领域中的一个经典研究方向，具有广泛的实际应用，如多处理器网络中的故障检测、传感器网络中的入侵者定位等。
  2. 现有码类型的局限: 文献中已有多种码的组合，包括：
    • 识别码(ID-codes): 闭邻域分离 + 支配
    • 定位支配码(LD-codes): 定位 + 支配
    • 开邻域分离全支配码(OTD-codes): 开邻域分离 + 全支配
  3. 研究空白: 开邻域分离与普通支配的组合(OD-code)此前未被系统研究，但这种组合在理论上是自然且必要的补充。

实际应用动机

  • 监控系统: 在建筑物监控中，当某些传感器被入侵者破坏时，需要使用开邻域分离性质来精确定位入侵者位置
  • 网络安全: 在网络拓扑中部署检测设备，确保能够识别和定位异常节点

核心贡献

  1. 引入新的码类型: 首次系统性地定义和研究开邻域分离支配码(OD-code)
  2. 建立理论基础: 证明了OD-码存在的充要条件，以及与其他码类型的关系
  3. 复杂性分析: 证明了OD-Code问题的NP完全性，以及判断OD-数与OTD-数是否相等的NP困难性
  4. 界限分析: 给出了OD-数的上下界，特别是证明了对于无开孪生顶点且无孤立顶点的n阶图G，有⌈log n⌉ ≤ γ_OD(G) ≤ n-1
  5. 图族比较: 在多个重要图族上比较了OD-码和OTD-码的性质
  6. 多面体理论: 提供了OD-码问题的超图覆盖重构，并研究了相关的多面体结构

方法详解

任务定义

给定图G = (V,E)，一个顶点子集C ⊆ V是开邻域分离支配码(OD-code)当且仅当：

  1. 支配性质: 对于每个顶点v ∈ V，Nv ∩ C ≠ ∅（闭邻域与C的交集非空）
  2. 开邻域分离性质: 对于每个顶点v ∈ V，N(v) ∩ C是唯一的（开邻域与C的交集互不相同）

其中N(v)表示顶点v的开邻域，Nv = N(v) ∪ {v}表示闭邻域。

理论框架

存在性分析

定理: 图G是OD-可接受的当且仅当G没有开孪生顶点。

开孪生顶点是指具有相同开邻域的不同顶点，即N(u) = N(v)且u ≠ v。

超图重构

论文将OD-码问题等价地重构为超图覆盖问题：

OD-超图 H_OD(G) = (V, F_OD)包含以下超边：

  • 所有顶点的闭邻域Nv
  • 所有不同顶点对的开邻域对称差N(u)△N(v)

其中A△B = (A\B) ∪ (B\A)表示对称差。

复杂性证明

论文通过从线性SAT(LSAT)问题的归约证明了OD-Code问题的NP完全性。构造的图具有以下性质：

  • 二部图
  • 最大度数为4
  • 围长至少为6

技术创新点

  1. 与OTD-码的精确关系: 证明了对于OTD-可接受图G，有γ_OTD(G) - 1 ≤ γ_OD(G) ≤ γ_OTD(G)
  2. Bondy定理的应用: 巧妙运用Bondy定理证明了OD-数的上界
  3. 簇理论方法: 通过去除冗余超边得到OD-簇，简化了问题的分析

实验设置

研究对象

论文主要通过理论分析研究了以下图族：

  • 完全图K_n
  • 团的不交并
  • k-团星图
  • 二部图(半图、k-双星图)
  • 分裂图(头部蜘蛛图、扩展细蜘蛛图)
  • 细太阳图

分析方法

  1. 构造OD-簇: 确定每个图族的OD-簇结构
  2. 计算覆盖数: 利用已知的超图覆盖理论计算最小覆盖数
  3. 比较分析: 与对应的OTD-数进行比较

实验结果

主要结果

完全图族

  • 完全图K_n (n ≥ 2): γ_OD(K_n) = n-1 = γ_OTD(K_n) (当n ≥ 3时)
  • 匹配kK_2: γ_OD(kK_2) = 2k-1 < 2k = γ_OTD(kK_2)

二部图族

  • 半图B_k: γ_OD(B_k) = 2k-1 < 2k = γ_OTD(B_k)
  • k-双星D_k (k ≥ 3): γ_OD(D_k) = 2k-1 < 2k = γ_OTD(D_k)

分裂图族

  • 细头部蜘蛛H_k (k ≥ 3): γ_OD(H_k) = k = γ_OTD(H_k)
  • 厚头部蜘蛛H̄_k (k ≥ 3): γ_OD(H̄_k) = k+1 = γ_OTD(H̄_k)
  • 扩展细蜘蛛E_k (k ≥ 4): γ_OD(E_k) = k < k+1 = γ_OTD(E_k)

极值结果

论文发现了达到理论界限的图族：

  • 上界达成: 完全图、半图及其不交并达到上界γ_OD(G) = |V(G)| - 1
  • 下界分析: 分裂图可以接近对数下界⌈log n⌉

重要发现

  1. 不可加性: 对于某些不连通图，γ_OD(G)大于其连通分量OD-数的和，这在其他码类型中不会出现
  2. 差异的NP困难性: 尽管OD-数和OTD-数最多相差1，但判断它们是否相等是NP困难的

相关工作

识别问题谱系

论文系统梳理了识别问题的发展脉络：

  1. 识别码(1998): Karpovsky等人首次提出
  2. 定位支配码(1988): Slater引入
  3. 全支配变体(2006): Haynes等人研究
  4. 开邻域变体(2002-2010): Honkala等人和Seo-Slater独立提出OTD-码

应用领域

  • 多处理器网络故障检测
  • 图的逻辑可定义性
  • 图同构问题的标准标记
  • 传感器网络入侵者定位

结论与讨论

主要结论

  1. 理论完备性: OD-码填补了识别问题理论框架中的空白，与其他码类型形成完整的理论体系
  2. 计算复杂性: OD-Code问题是NP完全的，即使在受限的图类上
  3. 与OTD-码的微妙关系: 两者数值相差至多1，但判断是否相等是困难的
  4. 图族分类: 在不同图族上，OD-数和OTD-数可能相等或不等，呈现丰富的组合结构

局限性

  1. 算法设计: 论文主要关注理论性质，缺少实际的近似算法或启发式方法
  2. 图族覆盖: 仍有许多重要图族(如树、格图等)的OD-数未被研究
  3. 参数化复杂性: 未探讨固定参数可处理性等精细复杂性分析

未来方向

  1. 算法研究: 设计OD-码的近似算法和精确算法
  2. 参数化分析: 研究以各种图参数为参数的固定参数算法
  3. 动态问题: 考虑图结构变化时OD-码的维护问题
  4. 应用拓展: 探索OD-码在实际网络问题中的应用

深度评价

优点

  1. 理论贡献: 系统性地建立了OD-码的理论基础，填补了重要的研究空白
  2. 方法创新: 巧妙运用超图覆盖理论和多面体方法分析问题
  3. 结果深度: 不仅给出了存在性和复杂性结果，还深入分析了与相关问题的精确关系
  4. 技术严谨: 证明严密，使用了多种高级的组合数学技巧

不足

  1. 实用性: 作为纯理论研究，缺少实际应用的算法实现和性能评估
  2. 图族局限: 研究的图族相对有限，许多实际重要的图类未被涉及
  3. 计算实验: 缺少大规模图上的计算实验验证理论结果

影响力

  1. 学术价值: 为识别问题领域提供了新的研究方向和理论工具
  2. 理论意义: 丰富了支配理论和图的标记理论
  3. 方法论贡献: 展示了超图覆盖方法在组合优化中的强大应用

适用场景

  1. 理论研究: 为从事图论和组合优化的研究者提供新的研究对象
  2. 网络设计: 在需要节点监控和故障检测的网络系统设计中有潜在应用
  3. 算法竞赛: 相关的组合问题可能出现在算法竞赛中

参考文献

论文引用了35篇相关文献，涵盖了识别问题的主要发展历程和技术方法，特别是：

  • 26 Karpovsky等人的识别码开创性工作
  • 32 Slater的定位支配码基础理论
  • 33 Seo-Slater的OTD-码研究
  • 2,4 Argiroffo等人的多面体方法
  • 31 Sassano的覆盖多面体理论

本论文在组合数学和图论领域做出了重要的理论贡献，系统建立了开邻域分离支配码的理论框架，为识别问题研究开辟了新的方向。虽然主要关注理论分析，但为后续的算法设计和实际应用奠定了坚实基础。