{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T13:55:40Z","timestamp":1762869340416,"version":"3.37.3"},"reference-count":38,"publisher":"EDP Sciences","issue":"5","license":[{"start":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T00:00:00Z","timestamp":1727136000000},"content-version":"vor","delay-in-days":23,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"The National Science Foundation of China","award":["12061059"],"award-info":[{"award-number":["12061059"]}]},{"name":"The Qinghai Key Laboratory of Internet of Things Project","award":["2017-ZJ-Y21"],"award-info":[{"award-number":["2017-ZJ-Y21"]}]},{"name":"the National Science Foundation of China","award":["12271259"],"award-info":[{"award-number":["12271259"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,3,10]]},"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:p>Let <jats:italic>G<\/jats:italic> be a graph with vertex set <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>) and edge set <jats:italic>E<\/jats:italic>(<jats:italic>G<\/jats:italic>). For a set <jats:italic>M<\/jats:italic> of vertices and an edge <jats:italic>e<\/jats:italic> of a graph <jats:italic>G<\/jats:italic>, let <jats:italic>P<\/jats:italic> (<jats:italic>M, e<\/jats:italic>) be the set of pairs (<jats:italic>x, y<\/jats:italic>) with a vertex <jats:italic>x<\/jats:italic> of <jats:italic>M<\/jats:italic> and a vertex <jats:italic>y<\/jats:italic> of <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>) such that <jats:italic>d<jats:sub>G<\/jats:sub><\/jats:italic>(<jats:italic>x, y<\/jats:italic>) <jats:italic>\u2260<\/jats:italic> <jats:italic>d<jats:sub>G\u2212e<\/jats:sub><\/jats:italic>(<jats:italic>x, y<\/jats:italic>). Given a vertex <jats:italic>x<\/jats:italic>, an edge <jats:italic>e<\/jats:italic> is said to be monitored by <jats:italic>x<\/jats:italic> if there exists a vertex <jats:italic>v<\/jats:italic> in <jats:italic>G<\/jats:italic> such that (<jats:italic>x, v<\/jats:italic>) <jats:italic>\u2208<\/jats:italic> <jats:italic>P<\/jats:italic> (<jats:italic>{x}, e<\/jats:italic>), and the collection of such edges is EM(<jats:italic>x<\/jats:italic>). A set <jats:italic>M<\/jats:italic> of vertices of a graph <jats:italic>G<\/jats:italic> is distance-edge-monitoring (DEM for short) set if every edge <jats:italic>e<\/jats:italic> of <jats:italic>G<\/jats:italic> is monitored by some vertex of <jats:italic>M<\/jats:italic>, that is, the set <jats:italic>P<\/jats:italic> (<jats:italic>M, e<\/jats:italic>) is nonempty. The DEM number dem(<jats:italic>G<\/jats:italic>) of a graph <jats:italic>G<\/jats:italic> is defined as the smallest size of such a set in <jats:italic>G<\/jats:italic>. The vertices of <jats:italic>M<\/jats:italic> represent distance probes in a network modeled by <jats:italic>G<\/jats:italic>; when the edge <jats:italic>e<\/jats:italic> fails, the distance from <jats:italic>x<\/jats:italic> to <jats:italic>y<\/jats:italic> increases, and thus we are able to detect the failure. In this paper, we first give some bounds or exact values of line graphs of trees, grids, complete bipartite graphs, and obtain the exact values of DEM numbers for some graphs and their line graphs, including the friendship and wheel graphs. Next, for each <jats:italic>n, m<\/jats:italic> &gt; 1, we obtain that there exists a graph <jats:italic>G<jats:sub>n,m<\/jats:sub><\/jats:italic> such that dem(<jats:italic>G<jats:sub>n,m<\/jats:sub><\/jats:italic>) = <jats:italic>n<\/jats:italic> and dem(<jats:italic>L<\/jats:italic>(<jats:italic>G<jats:sub>n,m<\/jats:sub><\/jats:italic>)) = 4 or 2<jats:italic>n<\/jats:italic> + <jats:italic>t<\/jats:italic>, for each integer <jats:italic>t<\/jats:italic> <jats:italic>\u2265<\/jats:italic> 0. In the end, the DEM number for the line graph of a small-world network (DURT) is given.<\/jats:p>","DOI":"10.1051\/ro\/2024106","type":"journal-article","created":{"date-parts":[[2024,5,15]],"date-time":"2024-05-15T08:24:45Z","timestamp":1715761485000},"page":"3715-3732","source":"Crossref","is-referenced-by-count":5,"title":["Realizability problem of distance-edge-monitoring numbers"],"prefix":"10.1051","volume":"58","author":[{"given":"Zhen","family":"Ji","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9134-237X","authenticated-orcid":false,"given":"Yaping","family":"Mao","sequence":"additional","affiliation":[]},{"given":"Eddie","family":"Cheng","sequence":"additional","affiliation":[]},{"given":"Xiaoyan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2024,9,24]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1080\/09728600.2022.2093146","volume":"19","author":"Bagga","year":"2022","journal-title":"AKCE Int. J. Graphs Comb."},{"key":"R2","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.jcss.2014.06.003","volume":"81","author":"Bampas","year":"2015","journal-title":"J. Comput. System Sci."},{"key":"R3","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/jgt.3190030410","volume":"3","author":"Bauer","year":"1979","journal-title":"J. Graph Theory"},{"key":"R4","doi-asserted-by":"crossref","first-page":"2168","DOI":"10.1109\/JSAC.2006.884015","volume":"24","author":"Beerliova","year":"2006","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"R5","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1109\/TNET.2006.882907","volume":"14","author":"Bejerano","year":"2006","journal-title":"IEEE\/ACM Trans. Netw."},{"doi-asserted-by":"crossref","unstructured":"Bhattacharya I. and Gupta S., Intelligent friendship graphs: a theoretical framework, in International Conference on Soft Computing and its Engineering Applications(icSoftComp). Springer International Publishing, Cham (2021) 90\u2013102.","key":"R6","DOI":"10.1007\/978-3-031-05767-0_8"},{"key":"R7","doi-asserted-by":"crossref","first-page":"1626","DOI":"10.1016\/j.tcs.2010.01.010","volume":"411","author":"Bil\u00f2","year":"2010","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Bondy J.A., Murty U.S.R., Graph Theory, GTM 244. Springer (2008).","key":"R8","DOI":"10.1007\/978-1-84628-970-5"},{"key":"R9","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1002\/jgt.3190020313","volume":"2","author":"Capobianco","year":"1978","journal-title":"J. Graph Theory"},{"doi-asserted-by":"crossref","unstructured":"Chapman A., Semi-Autonomous Networks: Controllability and Observability of Cartesian Product Networks. Springer (2015).","key":"R10","DOI":"10.1007\/978-3-319-15010-9_7"},{"key":"R11","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/BF01350320","volume":"182","author":"Chartrand","year":"1969","journal-title":"Math. Ann."},{"key":"R12","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/S0020-0190(00)00118-6","volume":"76","author":"Comellas","year":"2000","journal-title":"Inf. Process Lett."},{"key":"R13","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/j.tcs.2005.12.009","volume":"355","author":"Dall\u2019Asta","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"R14","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1007\/s11277-013-1334-2","volume":"74","author":"Fiaz","year":"2014","journal-title":"Wirel. Pers. Commun."},{"key":"R15","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/j.dam.2021.07.002","volume":"319","author":"Foucaud","year":"2022","journal-title":"Discrete Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"Govindan R. and Tangmunarunkit H., Heuristics for Internet map discovery, in Proceedings of the 19th IEEE International Conference on Computer Communications. INFOCOM\u201900. IEEE (2000) 1371\u20131380.","key":"R16","DOI":"10.1109\/INFCOM.2000.832534"},{"key":"R17","first-page":"191","volume":"2","author":"Harary","year":"1976","journal-title":"ARS Comb."},{"key":"R18","doi-asserted-by":"crossref","first-page":"115101","DOI":"10.1088\/1751-8113\/49\/11\/115101","volume":"49","author":"Hou","year":"2016","journal-title":"Phys. A"},{"key":"R19","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/j.dam.2023.09.020","volume":"342","author":"Ji","year":"2024","journal-title":"Discrete Appl. Math."},{"key":"R20","doi-asserted-by":"crossref","first-page":"056101","DOI":"10.1103\/PhysRevE.65.056101","volume":"65","author":"Jung","year":"2002","journal-title":"Phys. Rev. E"},{"key":"R21","first-page":"429","volume":"314","author":"Kelenc","year":"2017","journal-title":"Appl. Math. Comput."},{"key":"R22","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/j.dam.2018.05.052","volume":"251","author":"Kelenc","year":"2018","journal-title":"Discrete Appl. Math."},{"key":"R23","doi-asserted-by":"crossref","first-page":"2019","DOI":"10.1007\/s40840-016-0441-0","volume":"41","author":"Li","year":"2018","journal-title":"Bull. Malay. Math. Sci. Soc."},{"unstructured":"Li W., Klasing R., Mao Y. and Ning B., Monitoring the edges of product networks using distances. Available at arXiv: https:\/\/arxiv.org\/pdf\/2211.10743.pdf.","key":"R24"},{"key":"R25","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.physa.2011.08.002","volume":"391","author":"Lu","year":"2012","journal-title":"Phys. A"},{"key":"R26","doi-asserted-by":"crossref","first-page":"266403","DOI":"10.1103\/PhysRevLett.125.266403","volume":"125","author":"Ma","year":"2020","journal-title":"Phys. Rev. Lett."},{"key":"R27","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s41965-023-00131-y","volume":"5","author":"Mart\u00edn","year":"2023","journal-title":"J. Membr. Comput."},{"key":"R28","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.parco.2009.12.004","volume":"36","author":"Navaridas","year":"2010","journal-title":"Parallel Comput."},{"key":"R29","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/S0375-9601(99)00757-4","volume":"263","author":"Newman","year":"1999","journal-title":"Phys. Lett. A"},{"key":"R30","first-page":"23","volume":"5","author":"Parmar","year":"2017","journal-title":"Int. J. Math. Stat. Invention (IJMSI)"},{"key":"R31","first-page":"193","volume":"116","author":"Prizner","year":"1996","journal-title":"Congr. Numer."},{"key":"R32","first-page":"15","volume":"47","author":"Sarfraz","year":"2015","journal-title":"Punjab Univ. J. Math. (Lahore)"},{"key":"R33","first-page":"549","volume":"14","author":"Slater","year":"1975","journal-title":"Congr. Numer."},{"key":"R34","doi-asserted-by":"crossref","first-page":"2331","DOI":"10.1016\/j.comnet.2013.04.007","volume":"57","author":"Tarissan","year":"2013","journal-title":"Comput. Netw."},{"key":"R35","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.dam.2023.09.012","volume":"342","author":"Yang","year":"2024","journal-title":"Discrete Appl. Math."},{"key":"R36","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/s00236-024-00453-z","volume":"61","author":"Yang","year":"2024","journal-title":"Acta Inf."},{"key":"R37","doi-asserted-by":"crossref","first-page":"2891","DOI":"10.1093\/cercor\/bhn047","volume":"18","author":"Yu","year":"2008","journal-title":"Cereb. Cortex"},{"key":"R38","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1140\/epjb\/e2008-00262-2","volume":"63","author":"Zhang","year":"2008","journal-title":"Eur. Phys. J. B"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024106\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T08:00:11Z","timestamp":1727164811000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":38,"journal-issue":{"issue":"5"},"alternative-id":["ro230342"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024106","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,9]]}}}