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

Basic Information

Paper ID: 2211.10743
Title: Monitoring the edges of product networks using distances
Authors: Wen Li, Ralf Klasing, Yaping Mao, Bo Ning
Classification: cs.DM (Discrete Mathematics), cs.NI (Networking and Internet Architecture), math.CO (Combinatorics)
Publication Date: February 7, 2024 (arXiv v2)
Paper Link: https://arxiv.org/abs/2211.10743

Abstract

This paper investigates a novel graph-theoretic concept in network monitoring—distance edge monitoring. For a subset M of the vertex set V(G) of graph G and an edge e, P(M,e) is defined as the set of vertex pairs (x,y) satisfying $d_G(x,y) \neq d_{G-e}(x,y)$ , where $x \in M$ and $y \in V(G)$ . A set M is called a distance edge monitoring set if every edge e of graph G is monitored by some vertex in M (i.e., P(M,e) is non-empty). This paper primarily investigates the distance edge monitoring numbers of Cartesian products, joins, corona graphs, and clusters, providing exact bounds and characterization results.

Research Background and Motivation

Problem Background

Network Monitoring Requirements: In real-world networks, it is necessary to monitor network connections (edges) for failures and detect them when a connection fails. This is critical for fundamental tasks such as routing and network verification.
Distance Probing: Using distance probing to measure distances in networks is a common practice. The goal is to select a minimum set of vertices as probes that can monitor all edges in the network.
Theoretical Foundation: Foucaud et al. recently introduced the concept of distance edge monitoring, providing a new graph-theoretic tool for network monitoring.

Research Motivation

Existing network monitoring methods are primarily based on traditional graph parameters such as vertex cover, lacking a specialized theoretical framework for edge fault detection
There is a need to study the impact of graph operations (particularly Cartesian products) on distance edge monitoring numbers
Exact calculations of distance edge monitoring numbers for specific network topologies are lacking

Core Contributions

Bounds for Cartesian Products: Proved that for two graphs G and H, the distance edge monitoring number of their Cartesian product $G \square H$ satisfies: $\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)$
Characterization of Bounds: Completely characterized the necessary and sufficient conditions for graphs achieving the upper and lower bounds
Other Graph Operations: Determined the distance edge monitoring numbers for join, corona, and cluster operations
Specific Network Calculations: Provided exact distance edge monitoring numbers for basic graph classes such as paths, cycles, complete graphs, and their Cartesian products

Methodology Details

Task Definition

Distance Edge Monitoring Set: For a graph G, a vertex set M ⊆ V(G) is called a distance edge monitoring set if for every edge e of G, there exist vertices x ∈ M and y ∈ V(G) such that $d_G(x,y) \neq d_{G-e}(x,y)$ .

Distance Edge Monitoring Number: Denoted as dem(G), the size of the minimum distance edge monitoring set.

Core Theoretical Framework

1. Analysis of Cartesian Product Properties

For vertices $w_{i,j}$ and $w_{i',j'}$ in $G \square H$ , the distance formula is: $d_{G \square H}(w_{i,j}, w_{i',j'}) = d_G(u_i, u_{i'}) + d_H(v_j, v_{j'})$

2. Monitoring Set Decomposition

Theorem 3.2: For edges and monitoring sets M in $G \square H$ :

$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})$

This demonstrates that edge monitoring in Cartesian products can be decomposed to corresponding subgraphs.

3. Bound Proof Strategy

Lower Bound Proof: By contradiction, assuming the existence of a monitoring set smaller than the lower bound, there must exist a subgraph lacking sufficient monitoring vertices, causing certain edges in that subgraph to remain unmonitored.

Upper Bound Proof: Constructive proof by rationally distributing monitoring vertices to various subgraphs, ensuring all edges are monitored.

Technical Innovations

Decomposition Technique: Decomposing the edge monitoring problem in Cartesian products into edge monitoring problems in subgraphs, significantly simplifying the analysis complexity
Tightness of Bounds: Not only providing bounds but also completely characterizing graph classes achieving the bounds
Unified Framework: Providing a unified analytical framework for multiple graph operations

Experimental Setup

Theoretical Verification

This paper is primarily theoretical research, verifying results through mathematical proofs, including:

Construction of specific examples achieving bounds
Counterexamples verifying bound tightness
Exact calculations for special graph classes

Specific Calculation Examples

Cartesian Product of Paths: $\text{dem}(P_m \square P_n) = \max\{m,n\}$
Cartesian Product of Trees and Cycles: $n & \text{if } n \geq 2m + 1 \\ 2m & \text{if } n \leq 2m \end{cases}$$$
Cartesian Product of Cycles: $\text{dem}(C_m \square C_n) = \max\{2m, 2n\}$

Experimental Results

Main Results

1. Exact Bounds for Cartesian Products

Theorem 3.4 establishes the dual bounds for the distance edge monitoring number of Cartesian products, which is the core result of this paper.

2. Conditions for Achieving Bounds

Upper Bound Achievement (Theorem 3.5): If and only if G or H has a unique distance edge monitoring set
Lower Bound Achievement (Theorem 3.8): Requires two technical conditions involving coverage properties of monitoring sets

3. Results for Other Graph Operations

Operation Type	Distance Edge Monitoring Number
Join $G \vee H$	$\min\{c(G) + n, c(H) + m\}$
Corona $G * H$	$m \cdot c(H)$
Cluster $G \odot H$	$\text{dem}(G) \leq \text{dem}(G \odot H) \leq m \cdot \text{dem}(H)$

Exact Values for Specific Networks

Book Graphs: $\text{dem}(B_n) = 2$ , with unique monitoring set
Cartesian Product of Complete Graphs: $\text{dem}(K_m \square K_n) = mn - \min\{m,n\}$
Grid Graphs: $\text{dem}(P_m \square P_n) = \max\{m,n\}$

Comparative Parameter Analysis

The paper also compares the distance edge monitoring number with other graph parameters:

Metric dimension
Edge metric dimension
Strong metric dimension

Results show these parameters are independent of each other, each with its application scenarios.

Origins of Distance Edge Monitoring

Foucaud et al. first introduced the concept of distance edge monitoring in 2022, establishing the foundational theoretical framework:

Proved that $1 \leq \text{dem}(G) \leq n-1$
Characterized cases where $\text{dem}(G) = 1$ (if and only if G is a tree) and $\text{dem}(G) = n-1$ (if and only if G is a complete graph)
Proved that computing the distance edge monitoring number is NP-complete

Graph Product Research

Graph products, as tools for combining two known graphs to obtain new graphs, have been extensively studied in graph theory:

Cartesian product is one of the most important graph product operations
Has important applications in network design and parallel computing
This paper is the first systematic study of distance edge monitoring properties of graph products

Network verification through routing table queries
Network discovery based on shortest path queries
Network topology inference and fault detection

Conclusions and Discussion

Main Conclusions

Theoretical Breakthrough: Established a complete theoretical framework for the distance edge monitoring number of Cartesian products, providing exact dual bounds
Characterization Theorems: Completely characterized graph classes achieving the bounds, providing theoretical guidance for practical applications
Computational Results: Determined exact distance edge monitoring numbers for multiple important graph classes and operations

Limitations

Computational Complexity: Although theoretical results are provided, computing the distance edge monitoring number remains NP-complete
Practical Applications: There remains a gap between theoretical results and practical network applications
Approximation Algorithms: Lack of efficient approximation algorithm designs

Future Directions

The paper explicitly identifies several important research directions:

Graph Class Extensions: Study distance edge monitoring numbers for pyramid graphs, Sierpiński-type graphs, circulant graphs, line graphs, etc.
Parameter Characterization: Characterize graph classes satisfying $\text{dem}(G) = n-2$
Parameter Relationships: Further clarify relationships between distance edge monitoring numbers and tree degree, vertex cover, feedback edge set, and other parameters
Algorithm Design: Develop better approximation algorithms and fixed-parameter algorithms

In-Depth Evaluation

Strengths

Theoretical Completeness: The paper establishes a complete theoretical system for distance edge monitoring of Cartesian products, with rigorous and in-depth results
Technical Innovation: The decomposition technique and bound characterization methods are highly innovative, providing new insights for related problem research
Result Precision: Not only providing bounds but also completely characterizing necessary and sufficient conditions for achieving bounds, making theoretical results highly precise
Broad Applicability: The studied graph operations have wide applications in network design, and theoretical results have practical value

Weaknesses

Missing Experimental Verification: As pure theoretical research, lacks experimental verification on real networks
Algorithm Level: Primarily focuses on theoretical bounds with insufficient attention to algorithm design
Complexity Analysis: Lacks detailed computational complexity analysis for new graph operations

Impact

Theoretical Contribution: Establishes important theoretical foundations for this emerging field of distance edge monitoring
Methodological Value: The decomposition technique and characterization methods provide valuable references for research on other graph parameters
Application Prospects: Has potential applications in network monitoring and fault detection

Applicable Scenarios

Network Design: Provides theoretical guidance for designing network topologies with good monitoring properties
Fault Detection: Direct application in network systems requiring edge fault detection
Theoretical Research: Provides important theoretical tools for further research on related graph parameters

References

The paper cites 21 related references, primarily including:

Pioneering work by Foucaud et al. 8: Establishing foundational theory of distance edge monitoring
Classical textbooks on graph products 10,11: Providing theoretical foundations for graph product operations
Research on metric dimension 14,15,16,17: Providing benchmarks for parameter comparison
Application research on network monitoring 1,2,3,5,9: Demonstrating practical background of theoretical research

Overall Assessment: This is a high-quality theoretical research paper making important contributions to the emerging field of distance edge monitoring. The paper is theoretically rigorous with in-depth results, laying a solid foundation for subsequent research. Although it has some shortcomings in experimental verification and algorithm design, as a foundational theoretical work, its value is undeniable.