{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T12:29:47Z","timestamp":1762432187729,"version":"build-2065373602"},"reference-count":12,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2022,5,25]],"date-time":"2022-05-25T00:00:00Z","timestamp":1653436800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the Natural Science Foundation of China","award":["61902304"],"award-info":[{"award-number":["61902304"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>A new graph parameter, edge neighbor toughness is introduced to measure how difficult it is for a graph to be broken into many components through the deletion of the closed neighborhoods of a few edges. Let G=(V,E) be a graph. An edge e is said to be subverted when its neighborhood and the two endvertices are deleted from G. An edge set S\u2286E(G) is called an edge cut-strategy if all the edges in S has been subverted from G and the survival subgraph, denoted by G\/S, is disconnected, or is a single vertex, or is. The edge neighbor toughness of a graph G is defined to be tEN(G)=minS\u2286E(G){|S|c(G\/S)}, where S is any edge cut strategy of G, c(G\/S) is the number of the components of G\/S. In this paper, the properties of this parameter are investigated, and the proof of the computation problem of edge neighbor toughness is NP-complete; finally, a polynomial algorithm for computing the edge neighbor toughness of trees is given.<\/jats:p>","DOI":"10.3390\/axioms11060248","type":"journal-article","created":{"date-parts":[[2022,5,25]],"date-time":"2022-05-25T08:41:33Z","timestamp":1653468093000},"page":"248","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Edge Neighbor Toughness of Graphs"],"prefix":"10.3390","volume":"11","author":[{"given":"Xin","family":"Feng","sequence":"first","affiliation":[{"name":"School of Science, Xi\u2019an University of Architecture and Technology, Xi\u2019an 710055, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zongtian","family":"Wei","sequence":"additional","affiliation":[{"name":"School of Science, Xi\u2019an University of Architecture and Technology, Xi\u2019an 710055, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2228-2286","authenticated-orcid":false,"given":"Yucheng","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Digital Economy and Digital Technology, Shaanxi Youth Vocational College, Xi\u2019an 710100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,5,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0166-218X(85)90075-7","article-title":"On the Neighbor-Connectivity in Regular Graphs","volume":"11","author":"Gunther","year":"1985","journal-title":"Discret. Appl. Math."},{"key":"ref_2","first-page":"199","article-title":"Extreme Values of the Edge Neighbor-Connectivity","volume":"39","author":"Cozzens","year":"1995","journal-title":"Ars Comb."},{"key":"ref_3","first-page":"271","article-title":"Edge Neighbor-Scattering Number of Graphs","volume":"85","author":"Wei","year":"2007","journal-title":"Ars Comb."},{"key":"ref_4","first-page":"417","article-title":"Vertex Neighbor-Scattering Number of Graphs","volume":"102","author":"Wei","year":"2011","journal-title":"Ars Comb."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., and Murty, U.S.R. (1976). Graph Theory with Applications, Elsevier.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"ref_6","first-page":"163","article-title":"Edge-neighbour-integrity of trees","volume":"10","author":"Cozzens","year":"1994","journal-title":"Australas. J. Combin."},{"key":"ref_7","first-page":"364","article-title":"Edge Dominating Sets in Graphs","volume":"38","author":"Yannakakis","year":"1993","journal-title":"SIAM J. Discret. Math."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"599","DOI":"10.5560\/zna.2013-0059","article-title":"Computing the Edge Neighbour-Scattering Number of Graphs","volume":"68","author":"Wei","year":"2013","journal-title":"Z. Naturforschung A"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"19066","DOI":"10.1038\/srep19066","article-title":"On Wiener Polarity Index of Bicyclic Networks","volume":"6","author":"Ma","year":"2016","journal-title":"Sci. Rep."},{"key":"ref_10","first-page":"1019","article-title":"Note on Two Generalizations of the Randic Index","volume":"265","author":"Shi","year":"2015","journal-title":"Appl. Math. Comput."},{"key":"ref_11","first-page":"105","article-title":"Maximal Matching Energy of Tricyclic Graphs","volume":"73","author":"Chen","year":"2015","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Li, X., and Mao, Y. (2016). Generalized Connectivity of Graphs, Springer.","DOI":"10.1007\/978-3-319-33828-6"}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/11\/6\/248\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:18:36Z","timestamp":1760138316000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/11\/6\/248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,25]]},"references-count":12,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2022,6]]}},"alternative-id":["axioms11060248"],"URL":"https:\/\/doi.org\/10.3390\/axioms11060248","relation":{},"ISSN":["2075-1680"],"issn-type":[{"type":"electronic","value":"2075-1680"}],"subject":[],"published":{"date-parts":[[2022,5,25]]}}}