Abstract
It is important to be able to monitor the network and detect this failure when a connection (an edge) fails. For a vertex set M and an edge e of the graph G, let P(M, e) be the set of pairs (x, y) with a vertex x of M and a vertex y of V(G) such that e belongs to all shortest paths between x and y. A vertex set M of the graph G is 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 distance-edge-monitoring number of a graph G, recently introduced by Foucaud, Kao, Klasing, Miller, and Ryan, is defined as the smallest size of distance-edge-monitoring sets of G. In this paper, we determine the bounds of the distance-edge-monitoring number of grid-based pyramids and the exact value of distance-edge-monitoring number for M(t)-graph and Sierpiński-type graphs. We also compare the distance-edge-monitoring set with average degree, the size of edge set and the size of vertex set of G, where G is M(t)-graph or Sierpiński-type graphs.
Similar content being viewed by others
References
Biló, D., Erlebach, T., Mihalák, M., Widmayer, P.: Discovery of network properties with all-shortest-paths queries. Theoret. Comput. Sci. 411(14–15), 1626–1637 (2010)
Bampas, E., Biló, D., Drovandi, G., Gualá, L., Klasing, R., Proietti, G.: Network verification via routing table queries. J. Comput. System Sci. 81(1), 234–248 (2015)
Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihalák, M., Ram, L.S.: Network discovery and verification. IEEE J. Sel. Areas Commun. 24(12), 2168–2181 (2006)
Comellas, F., Miralles, A.: Modeling complex networks with self-similar outerplanar unclustered graphs. Phys. A 388(11), 2227–2233 (2009)
Comellas, F., Miralles, A., Liu, H., Zhang, Z.: The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs. Phys. A 392(12), 2803–2806 (2013)
Chang, J.-H.: An embedding of multiple edge-disjoint Hamiltonian cycles on enhanced pyramid graphs. J. Inform. Process. Syst. 7(1), 75–84 (2011)
Cao, F., Hsu, D.F.: Fault-tolerance properties of pyramid networks. IEEE Trans. Comput. 48, 88–93 (1999)
Dall’Asta, L., Alvarez-Hamelin, J.I., Barrat, A., Vázquez, A., Vespignani, A.: Exploring networks with traceroute-like probes: theory and simulations. Theoret. Comput. Sci. 355(1), 6–24 (2006)
Francesc, C., Alicia, M.: Vertex labeling and routing in self-similar outerplanar unclustered graphs modeling complex networks. J. Phys. A: Math. Theor. 42(42), 425001 (2009)
Foucaud, F., Kao, S., Klasing, R., Miller, M., Ryan, J.: Monitoring the edges of a graph using distances. Discrete Appl. Math. 319, 424–438 (2022)
Geetha, J., Somasundaram, K.: Total coloring of generalized Sierpiński graphs. Australas. J. Combin. 63(1), 58–69 (2015)
Govindan, R., Tangmunarunkit, H.: Heuristics for Internet map discovery. In: Proc. IEEE INFOCOM Conf. Comput. Commun. 19th Annu. Joint Conf. IEEE Comput. Commun. Soc., vol. 3. Tel Aviv, Israel, pp. 1371–1380 (2000)
Hoseinyfarahabady, M.R., Sarbazi-azad, H.: The grid-pyramid: a generalized pyramid network. J. Supercomput. 37, 23–45 (2006)
Juan, J.S.-T., Huang, C.-M.: On the strong distance problems of pyramid networks. Appl. Math. Comput. 195(1), 154–161 (2008)
Jeng, J.-F., Sahni, S.: Image shrinking and expanding on a pyramid. IEEE Trans. Parallel Distrib. Syst. 4, 1291–1296 (1993)
Miller, R., Stout, Q.: Data movement techniques for the pyramid computer. SIAM J. Comput. 16, 38–60 (1987)
Teguia, A.M., Godbole, A.P.: Sierpiński gasket graphs and some of their properties. Australas. J. Combin. 35, 181–192 (2006)
Zhang, Z., Zhou, S., Su, Z., et al.: Random Sierpiński network with scale-free small-world and modular structure. Eur. Phys. J. B 65(1), 141–147 (2008)
Funding
Supported by the National Science Foundation of China (Nos. 11601254, 11551001) and the Qinghai Key Laboratory of Internet of Things Project (2017-ZJ-Y21).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Yang, G., Zhou, J., He, C. et al. Distance-edge-monitoring sets of networks. Acta Informatica 61, 183–198 (2024). https://doi.org/10.1007/s00236-024-00453-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00236-024-00453-z