4等周边连通图的邻域条件

• 作 者: 徐子钧 张磊
• 机 构: 晋中学院数学学院
• 出 处: 太原师范学院学报：自然科学版
• 发表日期: 2016年2期
• 关键词: 互连网络 γk-最优图 k等周边连通度 邻域 interconnection networks γk-optimal graph k-isoperimetric

k等周边连通度是一个比边连通度更可靠的网络可靠性参数.连通图G的k等周边连通度定义为γ_k（G）=min{｜[X,X]｜：X■V（G）,｜X｜≥k,｜X｜≥k},其中珡X=V（G）／X.令βk（G）=min{｜[X,X]｜：X■V（G）,｜X｜=k}.图G是γ_k-最优的如果γ_k（G）=βk（G）.令G是一个阶至少为8的图.文章证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N（u）∩N（v）≥3;当u和v中至少有一个在三角形中时满足N（u）∩N（v）≥7,那么G是γ4-最优的