loading...
Computational complexity and bounds for neighbor-scattering number of graphs
Las Vegas, Nevada, USA December 07-December 09
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.308th International Symposium on Parall ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Fengwei Li, LPMC Nankai University,China
Xueliang Li, LPMC Nankai University,China
Let G = (V,E) be a graph. A vertex subversion strategy of G, X, is a set of vertices of G whose closed neighborhood is deleted from G. The survival-subgraph is de- fined by G/X. A vertex subversion strategy of G, X, is called a cut-strategy of G if the survival-subgraph is disconnected, or a clique, or \emptyset. The neighbor-scattering number of G, S(G), is defined as S(G) = max{w(G/X) - |X|: X is a cut-stragey of G w(G/X) \ge 1}, where w(G/X) is the number of connected components in the graph G/X. As a new graphic parameter, neighbor-scattering number can be used to measure the vulnerability of spy networks. In this paper, we prove that the problem of computing the neighbor-scattering number of a graph is NP-complete and discuss the upper and lower bounds for the neighbor-scattering number via some other well-known graphic parameters. Finally, we give formulas for the neighbor-scattering numbers of the join and union of two disjoint graphs.
Citation:
Fengwei Li, Xueliang Li, "Computational complexity and bounds for neighbor-scattering number of graphs," ispan, pp.478-483, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.