pith. sign in

arxiv: 2301.02507 · v4 · submitted 2023-01-06 · 💻 cs.DM · cs.DS· math.CO

Perturbation results for distance-edge-monitoring numbers

Chenxu Yang , Ralf Klasing , Changxiang He , Yaping Mao This is my paper

Pith reviewed 2026-05-24 09:49 UTC · model grok-4.3

classification 💻 cs.DM cs.DSmath.CO
keywords distance-edge-monitoringedge deletiongraph perturbationshortest pathsnetwork monitoringvertex deletion
0
0 comments X

The pith

Deleting an edge from any graph increases its distance-edge-monitoring number by at most 2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies how the smallest distance-edge-monitoring set changes size under edge or vertex deletions. It proves that for any graph G and edge e the quantity dem(G-e) is at most dem(G) plus 2, and exhibits graphs attaining equality. It also shows that vertex deletion can make the monitoring number jump by an arbitrary amount in either direction. The authors relate the parameter across subgraphs and supply an algorithm that checks whether a given monitoring set survives after any edge is removed.

Core claim

The central claim is that dem(G-e) − dem(G) ≤ 2 holds for every graph G and every edge e, with the bound sharp. The proof proceeds by examining how the removal of e affects the shortest-path containment relations that define which vertices monitor which edges.

What carries the argument

A distance-edge-monitoring set: a vertex subset M such that every edge lies on all shortest paths between some monitor in M and some other vertex.

If this is right

  • A network can be kept monitored after any single link failure by adding at most two extra monitors.
  • Vertex failures may demand arbitrarily many new monitors, so vertex and edge robustness differ sharply.
  • The monitoring number of a subgraph need not be close to that of the host graph.
  • An algorithm exists that decides, after any edge deletion, whether a candidate set still satisfies the monitoring property.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Designers of failure-tolerant networks may focus monitoring resources on edge stability rather than vertex stability.
  • It would be useful to characterize the graphs that attain the +2 increase.
  • The algorithmic check could be extended to dynamic settings where edges are added or removed repeatedly.

Load-bearing premise

The monitoring condition is defined using the standard shortest-path distances that remain after a single edge is deleted.

What would settle it

Any graph in which deleting one edge forces the addition of three or more new monitors to restore coverage of every remaining edge.

Figures

Figures reproduced from arXiv: 2301.02507 by Changxiang He, Chenxu Yang, Ralf Klasing, Yaping Mao.

Figure 1
Figure 1. Figure 1: The blue edges are those of trees T1 and T2 in K4. Example 1.21. Let G = K4 with V (G) = {v0, v1, v2, v3} and E(G) = {vivj | 0 ≤ i < j ≤ 3}. Let T1 and T2 be the subgraphs of G with E(T1) = {v0v1, v0v2, v0v3} and E(T2) = {v0v3, v3v1, v1v2}. Then, dem(K4|T1 ) = 1 and dem(K4|T2 ) = 2. The DEM set of subgraph Ti (i = 1, 2) in K4 is shown in [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The graph K(7, 12) We first give the proof of Proposition 1.10. Proof of Proposition 1.10: Let G = K(r, n) with V (G) = {ui | 0 ≤ i ≤ n − 1} and E(G) = {uiuj | 0 ≤ i < j ≤ r} ∪{ur+sur+s+1 | 0 ≤ s ≤ n − r − 2}. From Observation 1.1 and Theorem 1.7, we have dem(G) = dem(Gb) = dem(Kr+1) = r. In fact, for the above G, the path Pn−r−1 can be replaced by Tn−r−1, where Tn−r−1 is any tree of order n − r − 1. ⊓⊔ Pr… view at source ↗
Figure 3
Figure 3. Figure 3: dem(G∗ 8 ) = 6 [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 6
Figure 6. Figure 6 [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: For ℓ = 1, the graph C(1, k) is the wheel graph Wk, which is formed by connecting a single vertex c to all the vertices of cycle Ck. It is clear that |V (C(ℓ, k))| = kℓ + 1 and e(C(ℓ, k)) = 2kℓ. Lemma 4.2. Let n ≥ 3 be an integer. For v ∈ V (Cn), we have |EM(v) ∩ E(Cn)| = ( n − 1 if n is odd, n − 2 if n is even [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 7
Figure 7. Figure 7: The conical graph C(3, 8) Proof: Let G = Cn be cycle with V (G) = {vi | 1 ≤ i ≤ n} and E(G) = {vivi+1 | 1 ≤ i ≤ n − 1} ∪ {vnv1}. Without loss of generality, let v = v1. Suppose that n is odd and e1 = v⌊n/2⌋+1v⌊n/2⌋+2. Since dG(v1, v⌊n/2⌋+1) = dG−e1 (v1, v⌊n/2⌋+1) and dG(v1, v⌊n/2⌋+2) = dG−e1 (v1, v⌊n/2⌋+2), it follows that e1 ∈/ EM(v1). For any e ∈ {vivi+1 | 1 ≤ i ≤ ⌊n/2⌋}, since dG(v1, vi+1) ̸= dG−e(v1, v… view at source ↗
read the original abstract

Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Given a graph $G=(V(G), E(G))$, a set $M \subseteq V(G)$ is a distance-edge-monitoring set if for every edge $e \in E(G)$, there is a vertex $x \in M$ and a vertex $y \in V(G)$ such that the edge $e$ belongs to all shortest paths between $x$ and $y$. The smallest size of such a set in $G$ is denoted by $\operatorname{dem}(G)$. Denoted by $G-e$ (resp. $G \backslash u$) the subgraph of $G$ obtained by removing the edge $e$ from $G$ (resp. a vertex $u$ together with all its incident edges from $G$). In this paper, we first show that $\operatorname{dem}(G-e)- \operatorname{dem}(G)\leq 2$ for any graph $G$ and edge $e \in E(G)$. Moreover, the bound is sharp. Next, we construct two graphs $G$ and $H$ to show that $\operatorname{dem}(G)-\operatorname{dem}(G\setminus u)$ and $\operatorname{dem}(H\setminus v)-\operatorname{dem}(H)$ can be arbitrarily large, where $u \in V(G)$ and $v \in V(H)$. We also study the relation between $\operatorname{dem}(H)$ and $\operatorname{dem}(G)$, where $H$ is a subgraph of $G$. In the end, we give an algorithm to judge whether the distance-edge monitoring set still remain in the resulting graph when any edge of the graph $G$ is deleted.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies perturbation effects on the distance-edge-monitoring number dem(G) of a graph G. It proves that dem(G-e) - dem(G) ≤ 2 for any graph G and edge e, with the bound sharp. It constructs families of graphs showing that dem can change by arbitrarily large amounts under vertex deletion (in both directions). It examines how dem behaves under taking subgraphs and concludes with an algorithm to decide whether a given distance-edge-monitoring set remains valid after an arbitrary edge deletion.

Significance. The edge-removal bound of +2 (with matching lower-bound examples) is a clean, useful result for a monitoring parameter whose definition rests only on shortest-path containment. The contrast with arbitrary changes under vertex deletion is informative. The subgraph monotonicity discussion and the decision algorithm are natural extensions. If the proofs are correct, the work strengthens the foundations of distance-edge-monitoring and supplies concrete tools for analyzing network robustness under small modifications.

minor comments (3)
  1. [Abstract] The abstract states that the bound is sharp but gives no hint of the extremal graphs; a one-sentence description of the construction (or a forward reference) would improve readability.
  2. [Algorithm section] In the algorithm section, the decision procedure is described in prose; adding pseudocode or a clear enumeration of the steps would make the procedure easier to implement and verify.
  3. [Throughout] Notation for the monitoring set M and the pair (x,y) is introduced early but occasionally reused without re-stating the containment condition; a short reminder sentence at the start of each technical section would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation of minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives the bound dem(G-e) - dem(G) ≤ 2 directly from the definition of distance-edge-monitoring sets via shortest-path containment, with no fitted parameters, no self-referential definitions, and no load-bearing self-citations. All claims (including sharpness via explicit constructions and the decision algorithm) follow from standard graph operations and the initial concept introduced by Foucaud et al. (external citation). The derivation is self-contained against the given definitions and does not reduce any prediction to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests entirely on the standard definition of shortest paths and the newly introduced monitoring-set concept; no numerical parameters are fitted and no new entities are postulated.

axioms (1)
  • standard math Every pair of vertices in a connected graph has at least one shortest path.
    Invoked in the definition of distance-edge-monitoring set given in the abstract.

pith-pipeline@v0.9.0 · 5867 in / 1197 out tokens · 29437 ms · 2026-05-24T09:49:49.432064+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Network verification via routing table queries, J

    Bampas E, Bil `o D, Drovandi G, Gual `a L, Klasing R, Proietti G. Network verification via routing table queries, J. Comput. System Sci., 2015. 81(1):234–248. doi:10.1016/j.jcss.2014.06.003

    work page doi:10.1016/j.jcss.2014.06.003 2015

  2. [2]

    On the parameterized complexity of the edge monitoring problem, Inform

    Baste J, Beggas F, Kheddouci H, Sau I. On the parameterized complexity of the edge monitoring problem, Inform. Process. Lett., 2017. 121:39–44. doi:10.1016/j.ipl.2017.01.008

    work page doi:10.1016/j.ipl.2017.01.008 2017

  3. [3]

    Network discovery and verification, IEEE J

    Beerliova Z, Eberhard F, Erlebach T, Hall A, Hoffmann M, Mihal´ak M, Ram LS. Network discovery and verification, IEEE J. Sel. Areas Commun. , 2006. 24(12):2168–2181. doi:10.1109/JSAC.2006.884015

    work page doi:10.1109/jsac.2006.884015 2006

  4. [4]

    Discovery of network properties with all-shortest-paths queries, Theoret

    Bil `o D, Erlebach T, Mihal ´ak M, Widmayer P. Discovery of network properties with all-shortest-paths queries, Theoret. Comput. Sci., 2010. 411(14-15):1626–1637. doi:10.1016/j.tcs.2010.01.010

    work page doi:10.1016/j.tcs.2010.01.010 2010

  5. [5]

    Graphs & digraphs, London: Chapman & Hall, 2015

    Chartrand G, Lesniak L, Zhang P. Graphs & digraphs, London: Chapman & Hall, 2015. doi:10.1201/ b19731

    work page 2015

  6. [6]

    The theory and applications of resolvability in graphs–A Survey, Congr

    Chartrand G, Zhang P. The theory and applications of resolvability in graphs–A Survey, Congr . Numer .,

    work page

  7. [7]

    ID:125932758

    160:47–68. ID:125932758

    work page

  8. [8]

    Exploring networks with traceroute-like probes: Theory and simulations, Theoret

    Dall’Asta L, Alvarez-Hamelin J, Barrat A, V ´azquez A, Vespignani A. Exploring networks with traceroute-like probes: Theory and simulations, Theoret. Comput. Sci., 2006. 355(1):6–24. doi:10.1016/ j.tcs.2005.12.009

    work page 2006

  9. [9]

    The effect of vertex and edge deletion on the in- dependence number of graphs, F .E.J

    Delen S, Zihni FE, Erdogan FO, Ayna HO, Cangul IN. The effect of vertex and edge deletion on the in- dependence number of graphs, F .E.J. of Appl. Math., 2022. 11(2):11–19. doi:10.17654/0972096022002

    work page doi:10.17654/0972096022002 2022

  10. [10]

    The effect of vertex or edge deletion on the metric dimension of graphs, J

    Eroh L, Feit P, Kang C, Yi E. The effect of vertex or edge deletion on the metric dimension of graphs, J. Combin. Optim., 2015. 6(4):433–444. doi:10.4310/JOC.2015.v6.n4.a2. Ch. Yang et al. / Perturbation Results for Distance-edge-monitoring Numbers 163

    work page doi:10.4310/joc.2015.v6.n4.a2 2015

  11. [11]

    Monitoring the edges of a graph using distances,Discrete Appl

    Foucaud F, Kao S, Klasing R, Miller M, Ryan J. Monitoring the edges of a graph using distances,Discrete Appl. Math., 2022. 319:424–438. doi:10.1016/j.dam.2021.07.002

    work page doi:10.1016/j.dam.2021.07.002 2022

  12. [12]

    Heuristics for Internet map discovery, Proceedings IEEE INFOCOM

    Govindan R, Tangmunarunkit H. Heuristics for Internet map discovery, Proceedings IEEE INFOCOM

    work page

  13. [13]

    Nineteenth Annual Joint Conference of the IEEE Com- puter and Communications Societies (Cat

    Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Com- puter and Communications Societies (Cat. No.00CH37064), 2000 pp. 1371–1380

    work page 2000

  14. [14]

    Erd˝os-Gallai-type problems for distance-edge-monitoring num- bers, Discrete Appl

    Ji Z, Klasing R, Li W, Mao Y , Zhang X. Erd˝os-Gallai-type problems for distance-edge-monitoring num- bers, Discrete Appl. Math., 2024. 342:275–285

    work page 2024

  15. [15]

    Monitoring the edges of product networks using distances, 2022

    Li W, Klasing R, Mao Y , Ning B. Monitoring the edges of product networks using distances, 2022. arXiv:2211.10743

    work page arXiv 2022

  16. [16]

    The effects of vertex deletion and edge deletion on the clique partition number, Ars Comb

    Monson SD. The effects of vertex deletion and edge deletion on the clique partition number, Ars Comb. 42, 1996

    work page 1996

  17. [17]

    The effect of vertex and edge deletion on the edge metric dimension of graphs

    Wei M, Yue J, Chen L. The effect of vertex and edge deletion on the edge metric dimension of graphs. J. Comb. Optim., 2022. 44:331–342. doi:10.1007/s10878-021-00838-7

    work page doi:10.1007/s10878-021-00838-7 2022

  18. [18]

    On the distance-edge-monitoring numbers of graphs,Discrete Appl

    Yang C, Klasing R, Mao Y , Deng X. On the distance-edge-monitoring numbers of graphs,Discrete Appl. Math., 2024. 342:153–167. doi:10.1016/j.dam.2023.09.012

    work page doi:10.1016/j.dam.2023.09.012 2024

  19. [19]

    Distance-edge-monitoring numbers of networks, accepted by Acta Infor- matica

    Yang G, Zhou J, He C, Mao Y . Distance-edge-monitoring numbers of networks, accepted by Acta Infor- matica

    work page

  20. [20]

    Diameter vulnerability of graphs by edge deletion,Discrete Math., 2009

    Ye H, Yang C, Xu J. Diameter vulnerability of graphs by edge deletion,Discrete Math., 2009. 309:1001–

    work page 2009

  21. [21]

    doi:10.1016/j.disc.2008.01.006

    work page doi:10.1016/j.disc.2008.01.006 2008