交错群图AG_n的h-外连通度  

h-Extra connectivity of alternating group graph AG_n

作　　者：林丽美[1,2] 周书明[1,2] 许力[1,2] 

机构地区：[1]福建师范大学数学与计算机科学学院,福建福州350007 [2]福建师范大学网络安全与密码技术重点实验室,福建福州350007

出　　处：《高校应用数学学报（A辑）》2013年第4期379-390,共12页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然基金项目(61072080);福建省基金项目(2013J01221;JA12073)

摘　　要：设G=(V,E)是一个图,F(?)V(G)是图G一个节点子集.如果G-F不连通且G-F的每一个连通分支都至少有h+1个节点,那么称F为G的一个h-外分离集.图G的h-外连通度,记作k_o^((h))(G),是图G的最小h-外分离集的基数,它能更有效地反应图的容错性.通过交错群图AG_n的容错性刻画,本文证明了交错群图AG_n的1-外连通度,2-外连通度和3-外连通度分别是4n-11,6n-19和8n-28.Let G = （V, E） be a graph with a subset F C V（G）. F is called a h-extra vertexseparting set of G if G - F is disconnected and each connected component of G - F has at least h ＋ 1 vertices. The h-extra vertex-connectivity of G, denoted by ko（h） （G）, is the cardinality of the minimum h- extra vertex-separting set of G, which can reflect the fault tolerance of the graph efficiently. Through the characterization of fault tolerance of alternating group graph AGn, this paper establishes that ko（1）（AGn） ： 4n - 11, ko（2）（AGn） ： 6n - 19, ko（3）（AGn） ： 8n - 28, respectively.

关 键 词：交错群图网络 容错性 h-外连通度 

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