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

详细信息    查看全文

• 作者：Yong Liu^a ; Zongtian Wei ; ^a ; ^{wzt6481@163.com" class="auth_mail" title="E-mail the corresponding author} ; Jiarong Shi^a ; Anchan Mai^b
• 关键词：Graph ; Edge-neighbor-scattering number ; Polynomial algorithm ; Tree
• 刊名：Applied Mathematics and Computation
• 出版年：2016
• 出版时间：20 June 2016
• 年：2016
• 卷：283
• 期：Complete
• 页码：1-5
• 全文大小：333 K

文摘

The edge-neighbor-scattering number (ENS) is an alternative invulnerability measure of networks such as the vertices represent spies or virus carriers. Let ve&_eid=1-s2.0-S0096300316301242&_mathId=si1.gif&_user=111111111&_pii=S0096300316301242&_rdoc=1&_issn=00963003&md5=1082ae0d5cb47731e5fd4bc72889c0b1" title="Click to view the MathML source">G=(V,E) be a graph and e be any edge in G. The open edge-neighborhood of e   is ve&_eid=1-s2.0-S0096300316301242&_mathId=si2.gif&_user=111111111&_pii=S0096300316301242&_rdoc=1&_issn=00963003&md5=e8fb90e1019247d6160174a818bc6b51" title="Click to view the MathML source">N(e)={f∈E(G)|f≠e,e and f are adjacent}, and the closed edge-neighborhood of e   is ve&_eid=1-s2.0-S0096300316301242&_mathId=si3.gif&_user=111111111&_pii=S0096300316301242&_rdoc=1&_issn=00963003&md5=7e75db746d904daf8f6cd3b25478757e" title="Click to view the MathML source">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 ve&_eid=1-s2.0-S0096300316301242&_mathId=si4.gif&_user=111111111&_pii=S0096300316301242&_rdoc=1&_issn=00963003&md5=7cbecec95fa5caeeff1abf9a91cf0192"> 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.