复合图P_m[G]的邻域完整度(英文)  

Vertex-neighbor-integrity of composition graph P_m[G]

作　　者：魏宗田[1] 翟美娟[1] 

机构地区：[1]西安建筑科技大学理学院,陕西西安710055

出　　处：《纺织高校基础科学学报》2007年第3期237-240,共4页Basic Sciences Journal of Textile Universities

基　　金：Supported by BSF in XAUAT(AJ12046)

摘　　要：设X是图G的顶点集的一个子集,如果从G中删去X的闭邻域中所有点,则称X为G的一个点颠覆策略.记幸存子图为G/X,G的邻域完整度定义为VNI(G)=min(|X|+r(G/X)},其中τ(G/X)表示G/X的最大连通分支所含顶点数.此参数是Cozzens和Wu为度量间谍网的脆弱性而引入的.Gambrell证明了此参数的计算问题是NP-完备的.讨论了路与任意图的复合图的邻域完整度的计算.A vertex subversion strategy of a graph G is a set of vertices Xlohtain in V （G） whose closed neighborhood is deleted from G. The survival subgraph is denoted by G/X. The vertex-neigh- bor-integrity of G is defined to be VNI（G）= min Xlohtain in V（G）{｜X｜ ＋τ（G/X）} ,where r（G/X） is the order of a largest component in G/X. This graph parameter was introduced by Cozzens and Wu to measure the vulnerability of spy networks. It was proved by Gambrell that the decision problem of computing the vertex-neighbor-integrity of a graph is NP-complete. In this paper, the vertex-neighbor-integrity of the composition graphs of a path and any graph is evaluated.

关 键 词：邻域完整度 复合图 路 点控制数 

分 类 号：O157.5[理学—数学]