点可迁图的限制边连通度  

作　　者：徐俊明[1] 

机构地区：[1]中国科学技术大学数学系,合肥230026

出　　处：《数学年刊（A辑）》2000年第5期605-608,共4页Chinese Annals of Mathematics

基　　金：国家自然科学基金!No.19971086;中国科学院基金!No.SLT9741

摘　　要：设Ｓ是连通图Ｇ的边子集．如果Ｇ－Ｓ不连通而且不含孤立点，那么称Ｓ是Ｇ的一个限制边割，Ｇ中所有限制边割中最小边数称为Ｇ的限制边连通度，记为λ＇（Ｇ）．限制边连通度是对传统边连通度的推广，而且是计算机互连网络容错性的一个重要度量．点可迁图是一类重要的网络模型．本文证明了如下结论： 设 Ｇ是连通的点可迁图．如果 Ｇ的点数ｎ≥ ４，而且点度ｋ≥ ２，那么或者λ＇（Ｇ）＝ ２ｋ－２，或者ｎ是偶数，Ｇ含三角形且存在整数ｍ≥２，使得ｋ≥λ＇（Ｇ）＝ｎ／ｍ≤２ｋ－３．

关 键 词：限制边连通度 点可迁图 互连网络 容错性 简单连通图 

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