Article ID Journal Published Year Pages File Type
473721 Computers & Mathematics with Applications 2007 8 Pages PDF
Abstract

Neighbour-scattering number is a useful measure for graph vulnerability. For some special kinds of graphs, explicit formulas are given for this number. However, for general graphs it is shown that to compute this number is NP-complete. In this paper, we prove that for interval graphs this number can be computed in polynomial time.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Preview
The neighbour-scattering number can be computed in polynomial time for interval graphs
Authors
, ,