Perturbation results for distance-edge-monitoring numbers

• Autorzy: Yang, Chenxu , Klasing, Ralf , He, Changxiang , Mao, Yaping
• Języki publikacji: EN

Abstrakty

EN

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 ⊆ V (G) is a distance-edge-monitoring set if for every edge e ∈ E(G), there is a vertex x ∈ M and a vertex y ∈ 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 dem(G). Denoted by G − e (resp. G\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 dem(G − e) − dem(G) ≤ 2 for any graph G and edge e ∈ E(G). Moreover, the bound is sharp. Next, we construct two graphs G and H to show that dem(G)−dem(G\u) and dem(H \v)−dem(H) can be arbitrarily large, where u ∈ V (G) and v ∈ V (H). We also study the relation between dem(H) and 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 a graph G is deleted.

Słowa kluczowe

EN

distance; perturbation result; distance-edge-monitoring set.

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2024
• Tom: Vol. 191, nr 2
• Strony: 141--163
• Opis fizyczny: Bibliogr. 18 poz., rys., tab.

Twórcy

autor

Yang, Chenxu

• School of Computer Qinghai Normal University Xining, Qinghai 810008, China,

autor

Klasing, Ralf

• Université de Bordeaux Bordeaux INP, CNRS, LaBRI UMR 5800, Talence, France ,

autor

He, Changxiang

• College of Science University of Shanghai for Science and Technology,

autor

Mao, Yaping

• Academy of Plateau Science and Sustainabilit and School of Mathematics and Statistics, Xining Qinghai 810008, China,

Bibliografia

• [1] Bampas E, Bilò D, Drovandi G, Gualà 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.
• [2] 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.
• [3] Beerliova Z, Eberhard F, Erlebach T, Hall A, Hoffmann M, Mihalák M, Ram LS. Network discovery and verification, IEEE J. Sel. Areas Commun., 2006. 24(12):2168-2181. doi:10.1109/JSAC.2006.884015.
• [4] Bilò D, Erlebach T, Mihalák 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.
• [5] Chartrand G, Lesniak L, Zhang P. Graphs & digraphs, London: Chapman & Hall, 2015. doi:10.1201/b19731.
• [6] Chartrand G, Zhang P. The theory and applications of resolvability in graphs–A Survey, Congr. Numer., 2003. 160:47-68. ID:125932758.
• [7] Dall’Asta L, Alvarez-Hamelin J, Barrat A, Vázquez 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.
• [8] Delen S, Zihni FE, Erdogan FO, Ayna HO, Cangul IN. The effect of vertex and edge deletion on the independence number of graphs, F.E.J. of Appl. Math., 2022. 11(2):11-19. doi:10.17654/0972096022002.
• [9] 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
• [10] 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.
• [11] Govindan R, Tangmunarunkit H. Heuristics for Internet map discovery, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), 2000 pp. 1371-1380.
• [12] Ji Z, Klasing R, Li W, Mao Y, Zhang X. Erdõs-Gallai-type problems for distance-edge-monitoring numbers, Discrete Appl. Math., 2024. 342:275-285.
• [13] Li W, Klasing R, Mao Y, Ning B. Monitoring the edges of product networks using distances, 2022. arXiv:2211.10743.
• [14] Monson SD. The effects of vertex deletion and edge deletion on the clique partition number, Ars Comb. 42, 1996.
• [15] 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.
• [16] 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.
• [17] Yang G, Zhou J, He C, Mao Y. Distance-edge-monitoring numbers of networks, accepted by Acta Informatica.
• [18] Ye H, Yang C, Xu J. Diameter vulnerability of graphs by edge deletion, Discrete Math., 2009. 309:1001-1006. doi:10.1016/j.disc.2008.01.006.

Identyfikatory

DOI

10.3233/FI-242176