Z. Naturforsch. **68a,** 599 – 604
(2013)

doi:10.5560/ZNA.2013-0059

Computing the Edge-Neighbour-Scattering Number of Graphs

Zongtian
Wei^{1},
Nannan
Qi^{2}, and
Xiaokui
Yue^{3}

^{1 }School of Science, Xi'an University of Architecture and Technology, Xi'an, Shaanxi 710055, P.R. China

^{2 }Science and Technology on EO-Control Laboratory, Luoyang Institute of Electro-Optic Equipment, Luoyang, Henan 471009, P.R. China

^{3 }School of Astronautics, Northwestern Polytechnical University, Xi'an, Shaanxi 710072, P.R. China

Received January 10, 2013 / revised April 7, 2013 / published online October 2, 2013

A set of edges *X* is subverted from a graph *G* by removing the closed neighbourhood *N*[*X*] from *G*. We denote the survival subgraph by *G*/*X*. An edge-subversion strategy *X* is called an edge-cut strategy of *G* if *G*/*X* is disconnected, a single vertex, or empty. The edge-neighbour-scattering number of a graph *G* is defined as *ENS*(*G*) = max{ω(*G*/*X*) - |*X*|: *X* is an edge-cut strategy of *G*}, where *ω*(*G*/*X*) is the number of components of *G*/*X*. This parameter can be used to measure the vulnerability of networks when some edges are failed, especially spy networks and virus-infected networks. In this paper, we prove that the problem of computing the
edge-neighbour-scattering number of a graph is **NP**-complete and give some upper and lower bounds for this parameter.

*Key words:* Vulnerability of Networks; Edge-Neighbour-Scattering Number; Computational Complexity; **NP**-Complete; Bounds.