图的孤立断裂度  

The Isolated Scattering Number of Graphs

作　　者：王世英[1] 杨玉星[2] 林上为[1] 李晶[1] 胡志明[1] 

机构地区：[1]山西大学数学科学学院,太原030006 [2]山西大学计算机与信息技术学院,太原030006

出　　处：《数学学报（中文版）》2011年第5期861-874,共14页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金资助项目(61070229)

摘　　要：连通图G的孤立断裂度isc(G)=max{i(G-S)-|S|:S∈C(G)},其中i(G-S)是G-S中的孤立点数,C(G)是G的点割集.本文研究了孤立断裂度和图的其它一些参数的关系.讨论了孤立断裂度取特殊值的一些图,证明了圈、连通二部图、连通二部图的联图以及树和圈的补图的孤立断裂度都达到最小.给出了具有给定阶数和最大度的村的最大、最小孤立断裂度.The isolated scattering number isc（G） = max{i（G - S） - ISI ： S ∈ C（G）},where G is a connected graph, i（G - S） is the number of isolated vertices of G - S and C（C） is the set of vertex cuts of C. In this paper, we investigate the relationships between the isolated scattering number and other parameters of a graph C, and discuss the graphs with special isolated scattering numbers. We prove that the isolated scattering numbers of a cycle, a connected bipartite graph, the join of connected bipartite graphs and the complement of a tree and a cycle are minimal, and give the maximum and minimum isolated scattering numbers of trees with given order and maximum degree.

关 键 词：网络 可靠性 孤立断裂度 

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