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

于志华; 黄晓晖; 梁晓东

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-01-21

- 一致最可靠完全多部图(英文)
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 28, Issue 2, Pages: 163-169(2011)
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：
  CLC： O157.5
- Published：2011
- 稿件说明：
移动端阅览
[1]于志华,黄晓晖,梁晓东.一致最可靠完全多部图(英文)[J].新疆大学学报(自然科学版),2011,28(02):163-169.

于志华, 黄晓晖, 梁晓东. 一致最可靠完全多部图(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2011, 28(2): 163-169.
[1]于志华,黄晓晖,梁晓东.一致最可靠完全多部图(英文)[J].新疆大学学报(自然科学版),2011,28(02):163-169. DOI：

于志华, 黄晓晖, 梁晓东. 一致最可靠完全多部图(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2011, 28(2): 163-169. DOI：

摘要

对于一个连通图G

假设边是可靠的而点以p的概率相互独立地发生故障.图G不连通的概率是一个多项式P(G

p).记作Ω (n

m)是有n个点

m条边的连通图的集合.如果对于任意的图H∈Ω (n

m)和任意实数p∈[0

P(G

p)≤P(H

p)成立

则称G是Ω (n

m)中的一致最可靠图.本文证明了完全k部图K(b

(b+1)k-3

(b+2)2)是它所在的类中的一致最可靠图.另外

还证明了对任意的h≥2

K(bh

(b+1)k-h-1

(b+2)1)不是其所属类中的一致最可靠图.

Abstract

For a connected graph G

suppose the edges are perfectly reliable while the vertices may fail independentlywith the same probability p.The probability of G being disconnected is a polynomial P(G

p) in p.Denote byΩ(n

m)the set of connected graphs with n vertices and m edges.A graph G ∈ Ω(n

m) is uniformly most reliable in its classif P(G

p) ≤ P(H

p) holds for any graph H ∈ Ω(n

m) and any real number p ∈ [0

1].In this paper

we prove that thecomplete k-partite graphs K(b

(b+1)k-3

(b+2)2) are uniformly most reliable in their classes

respectively.We also showthat K(bh

(b+1)k-h-1

(b+2)1) is not uniformly most reliable for any h ≥ 2.

关键词

Keywords

references

Amin A F,Slegrist K T,Slater P J.On the nonexistence of uniformly optimal graph for pair-connected reliability[J].Networks 1991,21:359-368.

Boesch F,Fclzer A.On the invulnerability of the regular complete k-partite graphs[J].SIAM J Appl Math,1971,20:176-182.

Boesch F.On unreliability polynomials and graph connectivity in reliable network synthesis[J].J Graph Theory,1986,10:339-352.

Boesch F,Satyanarayana A,Sufiel C.On residual connectedness network reliability[J].DIMACS series in Discrete Mathematics and Theo-retical Computer Science,Vol.5,American Mathematical Society 1991,51-59.

Boesch F,Li X,Suffel C.On the existence of uniformly optimally reliable networks[J].Networks,1991,21:181-194.

Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:North-Holland,1976.

Cao S,Li F,Jia Y.On the uniformly best graphs in the complete six-partite graphs[J].Journal of Guangxi Teachers Education University(Natural Science Edition)2008,28-32.

Goldschmidt O,Jaillet P,Lasota R.On reliablity of graphs with node failures[J].Networks 1994,24:251-259.

Harary F.The maximum connectivity of a graph[J].Proc Nat Acad Sci U S A,1962,48:1142-1146.

Kelmans A K.Crossing properties of graph reliability functions[J].J.Graph Theory,2000,35:206-221.

Liu S,Chen K,Liu X.Network reliablity with node failures[J].Networks,2000,35:109-117.

Myrvold W,Cheung K,Page L,et al.Uniformly-most reliable networks do not always exist[J].Networks 1991,21:417-419.

Sun H,Shao F,Zhang H,et al.A new class of uniformly best graphs in the complete tripartite graph(Chinese)[J].Journal of Dalian MaritimeUniversity,2005,31:105-108.

Sun H.The classes of uniformly optimially graphs in the complete tripapite and the complete 5-partite graphs(Chinese)[J].Disertation ofDalian Maritime University,2005.

Wang L.On the uniformly best networks and two algorithms for network reliability(Chinese)[J].Disertation of Dalian Martitime University,2005.

Yu S,Shao F,Meng H.Uniformly optimal graphs in some classes of graphs with node failures[J].Discrete Mathematics,2010,310:159-166.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

一类一致最优完全多部图

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

Related Author

马天龙

孟吉翔

张昭

Related Institution

No data

⁰