Edge Neighbor Toughness of Graphs
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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display=&...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-05-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/11/6/248 |
| _version_ | 1827662391946510336 |
|---|---|
| author | Xin Feng Zongtian Wei Yucheng Yang |
| author_facet | Xin Feng Zongtian Wei Yucheng Yang |
| author_sort | Xin Feng |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> be a graph. An edge <i>e</i> is said to be subverted when its neighborhood and the two endvertices are deleted from <i>G</i>. An edge set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>S</mi><mo>⊆</mo><mi>E</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> is called an edge cut-strategy if all the edges in <i>S</i> has been subverted from <i>G</i> and the survival subgraph, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>/</mo><mi>S</mi></mrow></semantics></math></inline-formula>, is disconnected, or is a single vertex, or is. The edge neighbor toughness of a graph <i>G</i> is defined to be <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>t</mi><mrow><mi>E</mi><mi>N</mi></mrow></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><munder><mo movablelimits="false" form="prefix">min</mo><mrow><mi>S</mi><mo>⊆</mo><mi>E</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></munder><mrow><mo>{</mo><mfrac><mrow><mo>|</mo><mi>S</mi><mo>|</mo></mrow><mrow><mi>c</mi><mo>(</mo><mi>G</mi><mo>/</mo><mi>S</mi><mo>)</mo></mrow></mfrac><mo>}</mo></mrow></mrow></semantics></math></inline-formula>, where <i>S</i> is any edge cut strategy of <i>G</i>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>c</mi><mo>(</mo><mi>G</mi><mo>/</mo><mi>S</mi><mo>)</mo></mrow></semantics></math></inline-formula> is the number of the components of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>/</mo><mi>S</mi></mrow></semantics></math></inline-formula>. In this paper, the properties of this parameter are investigated, and the proof of the computation problem of edge neighbor toughness is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mi>P</mi></mrow></semantics></math></inline-formula>-complete; finally, a polynomial algorithm for computing the edge neighbor toughness of trees is given. |
| first_indexed | 2024-03-10T00:25:24Z |
| format | Article |
| id | doaj.art-1e1a49ab97ee42bfb897dec73ba4fa0c |
| institution | Directory Open Access Journal |
| issn | 2075-1680 |
| language | English |
| last_indexed | 2024-03-10T00:25:24Z |
| publishDate | 2022-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Axioms |
| spelling | doaj.art-1e1a49ab97ee42bfb897dec73ba4fa0c2023-11-23T15:34:53ZengMDPI AGAxioms2075-16802022-05-0111624810.3390/axioms11060248Edge Neighbor Toughness of GraphsXin Feng0Zongtian Wei1Yucheng Yang2School of Science, Xi’an University of Architecture and Technology, Xi’an 710055, ChinaSchool of Science, Xi’an University of Architecture and Technology, Xi’an 710055, ChinaDepartment of Digital Economy and Digital Technology, Shaanxi Youth Vocational College, Xi’an 710100, ChinaA 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> be a graph. An edge <i>e</i> is said to be subverted when its neighborhood and the two endvertices are deleted from <i>G</i>. An edge set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>S</mi><mo>⊆</mo><mi>E</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> is called an edge cut-strategy if all the edges in <i>S</i> has been subverted from <i>G</i> and the survival subgraph, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>/</mo><mi>S</mi></mrow></semantics></math></inline-formula>, is disconnected, or is a single vertex, or is. The edge neighbor toughness of a graph <i>G</i> is defined to be <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>t</mi><mrow><mi>E</mi><mi>N</mi></mrow></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><munder><mo movablelimits="false" form="prefix">min</mo><mrow><mi>S</mi><mo>⊆</mo><mi>E</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></munder><mrow><mo>{</mo><mfrac><mrow><mo>|</mo><mi>S</mi><mo>|</mo></mrow><mrow><mi>c</mi><mo>(</mo><mi>G</mi><mo>/</mo><mi>S</mi><mo>)</mo></mrow></mfrac><mo>}</mo></mrow></mrow></semantics></math></inline-formula>, where <i>S</i> is any edge cut strategy of <i>G</i>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>c</mi><mo>(</mo><mi>G</mi><mo>/</mo><mi>S</mi><mo>)</mo></mrow></semantics></math></inline-formula> is the number of the components of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>/</mo><mi>S</mi></mrow></semantics></math></inline-formula>. In this paper, the properties of this parameter are investigated, and the proof of the computation problem of edge neighbor toughness is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mi>P</mi></mrow></semantics></math></inline-formula>-complete; finally, a polynomial algorithm for computing the edge neighbor toughness of trees is given.https://www.mdpi.com/2075-1680/11/6/248graphedge neighbor toughnessNP-completepolynomial algorithmtree |
| spellingShingle | Xin Feng Zongtian Wei Yucheng Yang Edge Neighbor Toughness of Graphs Axioms graph edge neighbor toughness NP-complete polynomial algorithm tree |
| title | Edge Neighbor Toughness of Graphs |
| title_full | Edge Neighbor Toughness of Graphs |
| title_fullStr | Edge Neighbor Toughness of Graphs |
| title_full_unstemmed | Edge Neighbor Toughness of Graphs |
| title_short | Edge Neighbor Toughness of Graphs |
| title_sort | edge neighbor toughness of graphs |
| topic | graph edge neighbor toughness NP-complete polynomial algorithm tree |
| url | https://www.mdpi.com/2075-1680/11/6/248 |
| work_keys_str_mv | AT xinfeng edgeneighbortoughnessofgraphs AT zongtianwei edgeneighbortoughnessofgraphs AT yuchengyang edgeneighbortoughnessofgraphs |