A polynomial algorithm of edge-neighbor-scattering number of trees

• Published in: Applied mathematics and computation 2016-06, Vol.283, p.1-5
• Main Authors: Liu, Yong, Wei, Zongtian, Shi, Jiarong, Mai, Anchan
• Format: Article
• Language: English
• Subjects: Algorithms; Computation; Edge-neighbor-scattering number; Graph; Graph theory; Graphs; Polynomial algorithm; Polynomials; Strategy; Survival; Tree; Trees
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2016.02.021

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∈E(G)|f≠e,e and f are adjacent}, and the closed edge-neighborhood of e is N[e]=N(e)∪{e}. An edge e in G is said to be subverted when N[e] is deleted from G. An edge set X ⊆ 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 ϕ. The ENS of a graph G is defined as ENS(G)=maxX⊆E(G){ω(G/X)−|X|}, where X is any edge-cut-strategy of G, ω(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.