一类一致最优完全多部图

马天龙; 梁晓东

您当前的位置：

首页 >

文章列表页 >

一类一致最优完全多部图

更新时间：2026-01-21

- 一类一致最优完全多部图
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 30, Issue 2, Pages: 157-164(2013)
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：
  CLC： O157.5
- Published：2013
- 稿件说明：
移动端阅览
[1]马天龙,梁晓东.一类一致最优完全多部图[J].新疆大学学报(自然科学版),2013,30(02):157-164.

马天龙, 梁晓东. 一类一致最优完全多部图[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2013, 30(2): 157-164.
[1]马天龙,梁晓东.一类一致最优完全多部图[J].新疆大学学报(自然科学版),2013,30(02):157-164. DOI：

马天龙, 梁晓东. 一类一致最优完全多部图[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2013, 30(2): 157-164. DOI：

摘要

以(n

m)表示具有n个顶点m条边的图的集合.假设图G的边可靠

而顶点可靠的独立概率为p

若对于所有1 p∈(0

图G均为(n

m)中的最可靠图

则称G为一致最优图.本文证明了完全k-部图K(b

(b+2)k 1)在其图类中是一致最优的

而当i>3时

完全k-部图K(b

(b+2)k 2

b+i)在其图类中不是一致最优的.

Abstract

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

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 2

b+i) are not uniformly optimal in their classes.

关键词

Keywords

references

Colbourn C.The Combinatorics of Network Reliability[M].New York:Oxford University Press,1987.

Shier D R.Network reliability and algebraic structures[M].Oxford:University Press,1991.

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,Li X,Suffel C.On the existence of uniformly optimally reliable networks[J].Networks,1991,21:181-194.

Gross D,Saccoman J.Uniformly optimally reliable graphs[J].Networks,1998,31:217-225.

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

Petingi L,Saccoman J,Schoppmann L.Uniformly least reliable graphs[J].Networks,1996,27:125-131.

Boesch F,Satyanarayana A,Suffel C.On residual connectedness network reliability,in:DIMACS Series in Discrete Math-ematics and Theoretical Computer Science[J].American Mathematical Society,1991,5:51-59.

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

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

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

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

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

Stivaros C.On the residual node connectedness network reliability model[D].Ph.D.Dissertation,Dept of Electrical Engi-neering and Computer Science,Stevens Institute of Technology,1990.

Liang X D,Meng J X,Zhang Z.Uniformly optimal complete multi-partite graphs[J].Journal of Xinjiang University,2012,29:1-8.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

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

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

Related Author

孟吉翔

张昭

于志华

黄晓晖

Related Institution

No data

⁰