一类一致最优完全多部图  

A Class of Uniformly Optimality Complete Multi-partite Graphs

作　　者：马天龙[1] 梁晓东[1] 

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《新疆大学学报（自然科学版）》2013年第2期157-164,共8页Journal of Xinjiang University(Natural Science Edition)

基　　金：国家自然科学基金(11171283);新疆大学博士启动基金(090106)

摘　　要：以(n,m)表示具有n个顶点m条边的图的集合.假设图G的边可靠,而顶点可靠的独立概率为p,若对于所有1 p∈(0,1),图G均为(n,m)中的最可靠图,则称G为一致最优图.本文证明了完全k-部图K(b,(b+2)k 1)在其图类中是一致最优的,而当i>3时,完全k-部图K(b,(b+2)k 2,b+i)在其图类中不是一致最优的.Denote by Ω（n,m） the set of graphs with n vertices and m edges. For a graph G, suppose that edges never fail and vertices operate independently of each other with a constant probability p. The graph G is called uniformly optimal in Ω（n,m） if, for all vertex-failure probabilities 1-p ∈ （0,1）, the graph G is the most reliable graph. This paper proves that the complete k-partite graphs K（b, （b＋2）^k-1） are uniformly optimal in their classes, while for i ≥ 3, the complete k-partite graphs K（b, （b＋2）^k-1, b＋i） are not uniformly optimal in their classes.

关 键 词：网络可靠性 完全多部图 一致最优图 

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