一致最优完全多部图(英文)

Uniformly Optimal Complete Multi-partite Graphs

假设图G的边可靠,而顶点可靠的独立概率为p,以(n,m)表示具有n个顶点m条边的图的集合.若对于所有1 p∈(0,1),图G均为(n,m)中的最可靠图,则称G为一致最优图.本文证明了完全k部图K(b,(b+1)k h 1,(b+2)h)在其图类中是一致最优的,而当i≥3时,完全k部图K(b,(b+1)k h 2,(b+2)h,b+i)在其图类中不是一致最优的.

For a graph G, suppose that edges never fail and vertices operate independently of each other with a constant probability p. Denote by Ω（n, m） the set of graphs with n vertices and m edges. 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 ＋ 1）k-h-1, （b ＋ 2）h） are uniformly optimal in their classes, while for i 〉 3, the complete k-partite graphs K（b, （b ＋ 1）k-h-2, （b ＋ 2）h, b ＋ i） are not uniformly optimal in their classes.