纺织高校基础科学学报
紡織高校基礎科學學報
방직고교기출과학학보
BASIC SCIENCES JOURNAL OF TEXTILE UNIVERSITIES
2007年
3期
237-240
,共4页
邻域完整度%复合图%路%点控制数
鄰域完整度%複閤圖%路%點控製數
린역완정도%복합도%로%점공제수
vertex-neighbor-integrity%composition graph%path%vertex dominating number
设X是图G的顶点集的一个子集,如果从G中删去X的闭邻域中所有点,则称X为G的一个点颠覆策略.记幸存子图为G/X,G的邻域完整度定义为VNI(G)=minX(∪-)V(G){|X|+τ(G/X)} ,其中τ(G/X)表示G/X的最大连通分支所含顶点数.此参数是Cozzens 和Wu为度量间谍网的脆弱性而引入的.Gambrell证明了此参数的计算问题是NP-完备的.讨论了路与任意图的复合图的邻域完整度的计算.
設X是圖G的頂點集的一箇子集,如果從G中刪去X的閉鄰域中所有點,則稱X為G的一箇點顛覆策略.記倖存子圖為G/X,G的鄰域完整度定義為VNI(G)=minX(∪-)V(G){|X|+τ(G/X)} ,其中τ(G/X)錶示G/X的最大連通分支所含頂點數.此參數是Cozzens 和Wu為度量間諜網的脆弱性而引入的.Gambrell證明瞭此參數的計算問題是NP-完備的.討論瞭路與任意圖的複閤圖的鄰域完整度的計算.
설X시도G적정점집적일개자집,여과종G중산거X적폐린역중소유점,칙칭X위G적일개점전복책략.기행존자도위G/X,G적린역완정도정의위VNI(G)=minX(∪-)V(G){|X|+τ(G/X)} ,기중τ(G/X)표시G/X적최대련통분지소함정점수.차삼수시Cozzens 화Wu위도량간첩망적취약성이인입적.Gambrell증명료차삼수적계산문제시NP-완비적.토론료로여임의도적복합도적린역완정도적계산.
A vertex subversion strategy of a graph G is a set of vertices X(∪-)V (G)whose closed neighborhood is deleted from G.The surval subgraph is denoted by G/X. The vertex-neighbor-integrity of G is defined to be VNI(G)=(minx(∪-)(G)){│X│+τ(G/X)}，where τ(G/X)in 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.
