Computing the scattering number of graphs

被引：28

作者：

Zhang, SG ^{[1
]}

Li, XL ^{[1
]}

Han, XL ^{[1
]}

机构：

[1] Northwestern Polytech Univ, Dept Math Appl, Xian 710072, Peoples R China

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 2002年 / 79卷 / 02期

关键词：

scattering number; NP-complete problem; grids; Cartesian product;

D O I：

10.1080/00207160211919

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The scattering number of a noncomplete connected graph G is defined by s(G) = max{w(G-X)-\X\: Xsubset ofV(G), w(G-X) greater than or equal to2}, where w(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.

引用

页码：179 / 187

页数：9

共 19 条

[1]

Almasi GS, 1989, HIGHLY PARALLEL COMP

[2]

Barefoot C., 1987, J Comb Math Comb Comput, V1, P12

[3]

BAREFOOT CA, 1987, C NUMER, V58, P103

[4] RECOGNIZING TOUGH GRAPHS IS NP-HARD [J].

BAUER, D ;

HAKIMI, SL ;

SCHMEICHEL, E .

DISCRETE APPLIED MATHEMATICS, 1990, 28 (03) :191-195

[5]

Bondy J.A., 2008, GRAD TEXTS MATH

[6]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[7]

Cozzens M., 1995, P 7 INT C THEOR APPL, P111

[8]

FAUDREE R, 1994, CLAW FREE GRAPHS

[9] MAXIMUM CONNECTIVITY OF A GRAPH [J].

HARARY, F .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1962, 48 (07) :1142-&

[10] SCATTERING NUMBER AND EXTREMAL NON-HAMILTONIAN GRAPHS [J].

HENDRY, GRT .

DISCRETE MATHEMATICS, 1988, 71 (02) :165-175

← 1 2 →