复合图P_m[G]的邻域完整度(英文)
Vertex-neighbor-integrity of composition graph P_m[G]作者机构:西安建筑科技大学理学院陕西西安710055
出 版 物:《纺织高校基础科学学报》 (Basic Sciences Journal of Textile Universities)
年 卷 期:2007年第20卷第3期
页 面:237-240页
学科分类:07[理学] 0817[工学-化学工程与技术] 070104[理学-应用数学] 0805[工学-材料科学与工程(可授工学、理学学位)] 0701[理学-数学]
基 金: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-完备的.讨论了路与任意图的复合图的邻域完整度的计算.