|
Z. Naturforsch. 68a, 599 – 604
(2013)
doi:10.5560/ZNA.2013-0059
Computing the Edge-Neighbour-Scattering Number of Graphs
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
Reprint requests to: Z. W.; E-mail:
wzt6481@163.com
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.