网络G(G<sub>0</sub>,G<sub>1</sub>;M)关于极大连通的点容错度(英文)

孙高兴; 孟吉翔

doi:10.13568/j.cnki.651094.2018.03.006

您当前的位置：

首页 >

文章列表页 >

网络G(G₀,G₁;M)关于极大连通的点容错度(英文)

更新时间：2026-01-21

- 网络G(G₀,G₁;M)关于极大连通的点容错度(英文)
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 35, Issue 3, Pages: 284-288(2018)
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：10.13568/j.cnki.651094.2018.03.006
  CLC： O157.5
- Published：2018
- 稿件说明：
移动端阅览
[1]孙高兴,孟吉翔.网络G(G_0,G_1;M)关于极大连通的点容错度（英文）[J],2018,35(03):284-288.
[1]孙高兴,孟吉翔.网络G(G_0,G_1;M)关于极大连通的点容错度（英文）[J],2018,35(03):284-288. DOI： 10.13568/j.cnki.651094.2018.03.006.

DOI：10.13568/j.cnki.651094.2018.03.006.

摘要

我们通常用连通图来模拟互联网络

而图G的连通度是研究网络可靠性和容错性的一个重要参数.如果一个连通图G=(V

E)的连通度达到它的最小度

那么称这个图是极大连通的(简称为最优-κ).如果对于任意的满足|S|≤m的点子集S■V(G)

G-S仍然是最优-κ的

那么称图G是m-最优-κ的.图G的关于最优-κ性质的点容错度定义为使得图G是m-最优-κ的最大整数m

记作O_κ(G).本文给出了网络G(G0

G1;M)的关于最优-κ性质的点容错度的上下界

并确定了一些著名网络的点容错度.

Abstract

The interconnection networks are generally modeled by a connected graph G

and the connectivity of G is an important parameter for reliability and fault tolerance of the network. A connected graph G =(V

E) is maximally connected(or optimal-κ for short) if its connectivity attains its minimum degree. We define a optimal-κ graph G to be m-optimal-κ if G-S is still optimal-κ for any vertex subset S ■ V(G) with |S | ≤ m. The maximum integer of such m

denoted by O_κ(G)

is said to be the vertex fault tolerance of G with respect to the optimal-κ property. In this paper

we get the upper and lower bounds of the vertex fault tolerance for optimal-κ property of G(G0

G1; M) networks

from which we determine the exact values of O_κ(G) for some well-known networks.

关键词

Keywords

references

Hellwig A,Volkmann L.Maximally edge-connected and vertex-connected graphs and digraphs:A survey[J].Discrete Mathematics,2008,308:3265-3296.

Fabrega J,Fiol M.Extraconnectivity of graphs with large girth[J].Discrete Mathematics,1994,127:163-170.

Fabrega J,Fiol M.On the extraconnectivity of graphs[J].Discrete Mathematics,1996,155:49-57.

Hong Y,Meng J,Zhang Z.Edge fault tolerance of graphs with respect to super edge connectivity[J].Discrete Applied Mathematics,2012,160:579-587.

Cheng C,Hsieh S.Bounds for the extra edge connectivity of graphs[C].Computing and Combinatoics,COCOON 2015.Lecture Notes in Computer Science,Springer International Publishing,2015,9198:624-631.

Hong Y,Zhang Z.Vertex fault tolerance of optimal-κgraphs and super-κgraphs[J].Information Process Letter,2009,109:1151-1155.

Wang D,Lu M.Edge fault tolerance of super edge connectivity for three families of interconnection networks[J].Information Science,2012,188:260-268.

Hong Z,Xu J.Vulnerability of super edge-connected networks[J].Theoretical Computuper Science,2014,520:75-86.

秦德金,田应智,孟吉翔.圈的笛卡积的圈点连通度(英文)[J].新疆大学学报(自然科学版),2017,34(4):415-420.

田应智,孟吉翔,陈星.半传递重图的限制性边连通度(英文)[J].新疆大学学报(自然科学版),2018,35(1):34-41.

Li X,Xu J.Edge-fault tolerance of hypercube-like networks[J].Information Process Letter,2009,109:655-659.

Chen Y,Tan J.Restricted connectivity for three families of interconnection networks[J].Applied Mathematics Compututation,2007,188:1848-1855.

Chartrand G,Harary F.Planar permutation graphs[J].Annales de l’Institut Henri Poincar′e,B 1967,3:433-438.

Bondy J,Murty U.Graph Theory with Applications[M].London,New York:Macmillan and Elsevier,1976.

Abraham S,Padmanabham K.The twisted cube topolgy for muti-processors:a study in network asymmetry[J].Journal of Parallel and Distributed Computing,1991,13:104-110.

Yang X,Evans D,Megson G.The locally twisted cubes[J].International Journal of Computer Mathematics,2005,82:401-413.

Kulasinghe P.Connectivity of the crossed cube[J].Information Process Letter,1997,61:221-226.

Cull P,Larson S.The M¨obius cubes[J].IEEE Transactions on Computers,1992,44:513-524.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰

网络G(G0,G1;M)关于极大连通的点容错度(英文)

DOI：10.13568/j.cnki.651094.2018.03.006

摘要

Abstract

关键词

Keywords

references

网络G(G₀,G₁;M)关于极大连通的点容错度(英文)