所属单位：

理学院

发表刊物：

Applied Mathematics and Computation

关键字：

中文关键字：图；边邻域离散数；多项式算法；树，英文关键字：graph;edge-neighbor-scattering number;polynomial a

摘要：

The edge-neighbor-scattering number (ENS) is an alternative invulnerability measure of networks such as the vertices represent spies or virus carriers. Let G=(V,E) be a graph and e be any edge in G. The open edge-neighborhood of e is N(e)={f\in E(G)|f\neq e, e and f are adjacent}, and the closed edge-neighborhood of e is N[e]= N(e)\cup{e}. An edge e in G is said to be subverted when N[e] is deleted from G. An edge set X\subseteq E(G) is called an edge subversion strategy of $G$ if each of the edges in X has been subverted from G. The survival subgraph is denoted by G/X. An edge subversion strategy X is called an edge-cut-strategy of G if the survival subgraph G/X is disconnected, or is a single vertex, or is \phi$. The ENS of a graph G is defined as ENS(G)=\max{\omega(G/X)-|X|}, where X is any edge-cut-strategy of G, $\omega(G/X)$ is the number of the components of G/X. It is proved that the problem of computing the ENS of a graph is NP-complete. In this paper, we give a polynomial algorithm of ENS of trees.

备注：

SCI检索

合写作者：

麦安婵

第一作者：

史加荣,魏宗田,刘勇

论文类型：

期刊论文

卷号：

卷：283

期号：

期：1

页面范围：

页：1-5

是否译文：

否

发表时间：

2016-03-01