A Polynomial Algorithm of Edge-neighbor-scattering Number of Trees
- Release time:2024-08-09
- Hits:
-
-
-
Affiliation of Author(s):
理学院
-
-
Journal:
Applied Mathematics and Computation
-
-
-
Key Words:
中文关键字：图；边邻域离散数；多项式算法；树，英文关键字：graph;edge-neighbor-scattering number;polynomial a
-
Abstract:
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.
-
Note:
SCI检索
-
Co-author:
麦安婵
-
First Author:
shijiarong,weizongtian,liuyong
-
Indexed by:
Journal paper
-
-
-
-
-
-
Volume:
卷：283
-
Issue:
期：1
-
Page Number:
页：1-5
-
-
-
Translation or Not:
no
-
-
Date of Publication:
2016-03-01
-
-
