Find in Library

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.