Vertex-neighbour-integrity of composition graphs of paths and cycles

Zongtian Wei, Shenggui Zhang

科研成果: 期刊稿件文章同行评审

4 引用 (Scopus)

摘要

A vertex subversion strategy of a graph G is a set of vertices X∪ V(G) whose closed neighbourhood is deleted from G. The survival subgraph is denoted by G/X. The vertex-neighbour-integrity of G is defined to be VNI(G)=min{|X|+τ(G/X):X∪ V(G)}, where τ(G/X) is the maximum order of the components of G/X. This graph parameter was introduced by Cozzens and Wu to measure the vulnerability of spy networks. Gambrell proved that the decision problem of computing the vertex-neighbour-integrity of a graph is NP-complete. In this paper we evaluate the vertex-neighbour-integrity of the composition graphs of paths and cycles.

源语言英语
页(从-至)727-733
页数7
期刊International Journal of Computer Mathematics
85
5
DOI
出版状态已出版 - 5月 2008

指纹

探究 'Vertex-neighbour-integrity of composition graphs of paths and cycles' 的科研主题。它们共同构成独一无二的指纹。

引用此