2025-11-17T21:58:13.640722

Monitoring the edges of product networks using distances

Li, Klasing, Mao et al.

Foucaud {\it et al.} recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Let $G$ be a graph with vertex set $V(G)$, $M$ a subset of $V(G)$, and $e$ be an edge in $E(G)$, and let $P(M, e)$ be the set of pairs $(x,y)$ such that $d_G(x, y)\neq d_{G-e}(x, y)$ where $x\in M$ and $y\in V(G)$. $M$ is called a \emph{distance-edge-monitoring set} if every edge $e$ of $G$ is monitored by some vertex of $M$, that is, the set $P(M, e)$ is nonempty. The {\em distance-edge-monitoring number} of $G$, denoted by $\operatorname{dem}(G)$, is defined as the smallest size of distance-edge-monitoring sets of $G$. For two graphs $G,H$ of order $m,n$, respectively, in this paper we prove that $\max\{m\operatorname{dem}(H),n\operatorname{dem}(G)\} \leq\operatorname{dem}(G\,\Box \,H) \leq m\operatorname{dem}(H)+n\operatorname{dem}(G) -\operatorname{dem}(G)\operatorname{dem}(H)$, where $\Box$ is the Cartesian product operation. Moreover, we characterize the graphs attaining the upper and lower bounds and show their applications on some known networks. We also obtain the distance-edge-monitoring numbers of join, corona, cluster, and some specific networks.

academic

Monitoring the edges of product networks using distances

基本信息

论文ID: 2211.10743
标题: Monitoring the edges of product networks using distances
作者: Wen Li, Ralf Klasing, Yaping Mao, Bo Ning
分类: cs.DM (Discrete Mathematics), cs.NI (Networking and Internet Architecture), math.CO (Combinatorics)
发表时间: 2024年2月7日 (arXiv v2)
论文链接: https://arxiv.org/abs/2211.10743

摘要

本文研究了网络监控领域中一个新的图论概念——距离边监控。对于图G的顶点集V(G)的子集M和边e，定义P(M,e)为满足 $d_G(x,y) \neq d_{G-e}(x,y)$ 的顶点对 $(x,y)$ 的集合，其中 $x \in M$ ， $y \in V(G)$ 。如果图G的每条边e都被M中的某个顶点监控（即P(M,e)非空），则称M为距离边监控集。本文主要研究了图的Cartesian积、连接、冠状图、簇等操作的距离边监控数，并给出了精确的界限和特征化结果。

研究背景与动机

问题背景

网络监控需求：在现实网络中，需要监控网络连接（边）的故障，当某条连接失效时能够被检测到。这在路由、网络验证等基础任务中至关重要。
距离探测：使用距离探测来测量网络中的距离是常见做法。目标是选择最小的顶点集合作为探测器，能够监控网络中的所有边。
理论基础：Foucaud等人最近引入了距离边监控的概念，为网络监控提供了新的图论工具。

研究动机

现有的网络监控方法主要基于顶点覆盖等传统图论参数，缺乏专门针对边故障检测的理论框架
需要研究图运算（特别是Cartesian积）对距离边监控数的影响
缺乏对具体网络拓扑结构的距离边监控数的精确计算

核心贡献

Cartesian积的界限：证明了对于两个图G、H，其Cartesian积 $G \square H$ 的距离边监控数满足： $\max\{m \cdot \text{dem}(H), n \cdot \text{dem}(G)\} \leq \text{dem}(G \square H) \leq m \cdot \text{dem}(H) + n \cdot \text{dem}(G) - \text{dem}(G) \cdot \text{dem}(H)$
界限的特征化：完全刻画了达到上界和下界的图的充要条件
其他图运算：确定了连接(join)、冠状图(corona)、簇(cluster)等图运算的距离边监控数
具体网络计算：给出了路径、环、完全图等基本图类及其Cartesian积的精确距离边监控数

方法详解

任务定义

距离边监控集：对于图G，顶点集M ⊆ V(G)称为距离边监控集，如果对于G的每条边e，都存在顶点x ∈ M和顶点y ∈ V(G)，使得 $d_G(x,y) \neq d_{G-e}(x,y)$ 。

距离边监控数：记为dem(G)，是最小距离边监控集的大小。

核心理论框架

1. Cartesian积的性质分析

对于 $G \square H$ 中的顶点 $w_{i,j}$ 和 $w_{i',j'}$ ，距离公式为： $d_{G \square H}(w_{i,j}, w_{i',j'}) = d_G(u_i, u_{i'}) + d_H(v_j, v_{j'})$

2. 监控集分解

定理3.2：对于 $G \square H$ 中的边和监控集M：

$P_{G \square H}(M, w_{i,j}w_{i,j'}) = P_{H_i}(M \cap V(H_i), w_{i,j}w_{i,j'})$
$P_{G \square H}(M, w_{i,j}w_{i',j}) = P_{G_j}(M \cap V(G_j), w_{i,j}w_{i',j})$

这表明Cartesian积中的边监控可以分解到相应的子图中。

3. 界限证明策略

下界证明：通过反证法，假设存在小于下界的监控集，则必然存在某个子图缺乏足够的监控顶点，导致该子图中的某些边无法被监控。

上界证明：构造性证明，通过合理分配监控顶点到各个子图中，确保所有边都能被监控。

技术创新点

分解技术：将Cartesian积的边监控问题分解为子图的边监控问题，大大简化了分析复杂度
界限的紧致性：不仅给出了界限，还完全刻画了达到界限的图类
统一框架：为多种图运算提供了统一的分析框架

实验设置

理论验证

本文主要是理论研究，通过数学证明验证结果的正确性，包括：

构造达到界限的具体例子
反例验证界限的紧致性
特殊图类的精确计算

具体计算实例

路径的Cartesian积： $\text{dem}(P_m \square P_n) = \max\{m,n\}$
树与环的Cartesian积： $n & \text{if } n \geq 2m + 1 \\ 2m & \text{if } n \leq 2m \end{cases}$$$
环的Cartesian积： $\text{dem}(C_m \square C_n) = \max\{2m, 2n\}$

实验结果

主要结果

1. Cartesian积的精确界限

定理3.4确立了Cartesian积距离边监控数的双边界限，这是本文的核心结果。

2. 界限达成条件

上界达成（定理3.5）：当且仅当G或H中只有唯一的距离边监控集时
下界达成（定理3.8）：需要满足两个技术条件，涉及监控集的覆盖性质

3. 其他图运算结果

运算类型	距离边监控数
连接 $G \vee H$	$\min\{c(G) + n, c(H) + m\}$
冠状图 $G * H$	$m \cdot c(H)$
簇 $G \odot H$	$\text{dem}(G) \leq \text{dem}(G \odot H) \leq m \cdot \text{dem}(H)$