Computing the Scattering Number of Graphs

Author： Zhang Shenggui   Li Xueling   Han Xinglou  

Publisher： Taylor & Francis Ltd

ISSN： 0020-7160

Source： International Journal of Computer Mathematics, Vol.79, Iss.2, 2002-01, pp. : 179-187

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The scattering number of a noncomplete connected graph G is defined by s(G)= max{ω(G−X)−∣X∣: X⊂V(G), ω(G−X)≥2}, where ω(G−X) denotes the number of components of G−X. This parameter can be used to measure the vulnerability of networks. It shows not only the difficulty to break down the network but also the damage that has been caused. In this paper, we prove that the problem of computing the scattering number of a graph is NP-complete. At the same time, the scattering numbers of grids and those of Cartesian products of two complete graphs are determined.

Related content

The scattering number of thorn graphs

By Kirlangiç Alpay   Aytaç Aysun Ozan  

International Journal of Computer Mathematics, Vol. 81, Iss. 3, 2004-03 ,pp. : 299-311 (13)

Taylor & Francis Ltd

Access to resources Recommend Favorite

Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

By  

JOURNAL OF GRAPH THEORY, Vol. 79, Iss. 4, 2015-08 ,pp. : 282-299 (18)

John Wiley & Sons Inc

Access to resources Recommend Favorite

On the Minus Domination Number of Graphs

By Liu Hailong   Sun Liang  

Czechoslovak Mathematical Journal, Vol. 54, Iss. 4, 2004-12 ,pp. : 883-887 (5)

Springer Publishing Company

Access to resources Recommend Favorite

Radio number of ladder graphs

By Wang Haoli  

International Journal of Computer Mathematics, Vol. 88, Iss. 10, 2011-07 ,pp. : 2026-2034 (9)

Taylor & Francis Ltd

Access to resources Recommend Favorite

On the locatic number of graphs

By Salman Muhammad   Chaudhry Muhammad Anwar   Javaid Imran  

International Journal of Computer Mathematics, Vol. 90, Iss. 5, 2013-05 ,pp. : 912-920 (9)

Taylor & Francis Ltd

Access to resources Recommend Favorite