完全对换网络的限制连通度

运筹学学报 ›› 2013, Vol. 17 ›› Issue (3): 57-64.

完全对换网络的限制连通度

王国亮¹, 师海忠^1,*

1. 西北师范大学数学与统计学院, 兰州 730070

出版日期:2013-09-15 发布日期:2013-09-15
通讯作者: 师海忠 E-mail:shihaizhong@nwnu.edu.cn
基金资助:
甘肃省自然科学基金(No. ZS991-A25-017-G)

The restricted connectivity of complete-transposition networks

WANG Guoliang¹, SHI Haizhong^1,*

1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China

Online:2013-09-15 Published:2013-09-15

摘要/Abstract

摘要： 完全对换网络是基于 Cayley 图模型的一类重要互连网络. 一个图 G 的 k-限制点(边)连通度是使得 G-F 不连通且每个分支至少有 k 个顶点的最小点(边)子集 F 的基数, 记作 \kappa_{k}(\lambda_{k}). 它是衡量网络可靠性的重要参数之一, 也是图的容错性的一种精化了的度量. 一般地, 网络的 k-限制点(边)连通度越大, 它的连通性就越好. 证明了完全对换网络 CT_{n} 的 2-限制点(边)连通度和 3-限制点(边)连通度, 具体来说: 当 n\geq4 时, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6; 当 n\geq3 时, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.

关键词: 互连网络, Cayley图, 完全对换网络, 限制点连通度, 限制边连通度

Abstract: Complete-transposition networks are a class of important Cayley graphs in networks design. The k-restricted vertex(edge)-connectivity of a graph G is the minimum cardinality of a set of vertices (edges) in G whose removal results in disconnected and each component has at least k vertices, denoted by \kappa_{k}(\lambda_{k}). The k-restricted vertex(edge)-connectivity is one of the most parameters to evaluate the reliability of a network, it is also a refined measure of the fault tolerance of the graph. In general, the larger the k-restricted vertex(edge)-connectivity of a network, the more reliable the network. The paper proves that 2-restricted vertex(edge)-connectivity and 3-restricted vertex(edge)-connectivity of complete-transposition networks, that is, when n\geq4, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6, when n\geq3, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.

Key words: interconnection networks, Cayley graphs, complete-transposition networks, restricted vertex-connectivity, restricted edge-connectivity

中图分类号:

TP393

王国亮, 师海忠. 完全对换网络的限制连通度[J]. 运筹学学报, 2013, 17(3): 57-64.

WANG Guoliang, SHI Haizhong. The restricted connectivity of complete-transposition networks[J]. Operations Research Transactions, 2013, 17(3): 57-64.

参考文献

Bondy J A, Murty U S R. Graph Theory[M]. Berlin: Springer, 2008.
高随祥. 图论与网络流理论[M]. 北京: 高等教育出版社, 2009.
Lakshmivarahan S, Jwo J-S, Dhall S.K. Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey [J]. Parallel Computing, 1993, 19: 361-407.
师海忠. 互连网络的代数环模型 [D]. 北京: 中国科学院数学与系统科学研究院应用数学研究所, 1998.
师海忠, 牛攀峰, 马继勇, 等. 互连网络的向量图模型[J]. 运筹学学报, 2011, 15: 115-123.
Bondy J A, Murty U S R. Graph Theory[M]. Berlin: Springer, 2008.
吕长虹，张克民．无向 de-Bruijin 图的超级边连通性和限制性边连通度[J]．应用数学学报, 2002, 25：29-35.
Fabrega J, Fiol M A. Extraconnectivity of graphs with large girth [J]. Discrete Mathematics, 1994, 127(1/3): 163-170.
Bondy J A, Murty U S R. Graph Theory[M]. Berlin: Springer, 2008.
Yu X M, Huang X H. Restricted vertex connectivity of modified bubble-sort graphs [J]. 新疆大学学报, 2012, 29: 78-81.
Yang W H, Li H Z, Meng J X. Conditional connectivity of Cayley graphs by transposition trees [J]. Information Processing Letters, 2010, 110: 1027-1030.
Bondy J A, Murty U S R. Graph Theory[M]. Berlin: Springer, 2008.
Li H Z, Meng J X, Yang W H. 3-extraconnectivity of Cayley graphs generated by transposition generating trees [J]. 新疆大学学报, 2012, 28: 148-151.
Bondy J A, Murty U S R. Graph Theory[M]. Berlin: Springer, 2008.
Bondy J A, Murty U S R. Graph Theory[M]. Berlin: Springer, 2008.
赵元庆, 金显华. 星网的4-限制边连通度[J]. 计算机工程与应用, 2012, 48: 71-74.
徐敏, 经衿. Bubble-sort 网络的连通度和超连通度[J]. 应用数学学报, 2012, 5: 789-794.
徐俊明. 组合网络理论[M]. 北京: 科学出版社, 2007.
Bondy J A, Murty U S R. Graph Theory[M]. Berlin: Springer, 2008.
王铭, 李乔. 可迁图的超常边连通度的最优性[J]. 数学年刊, 2003, 24A: 315-320.
Cheng E, Liptak L. Fault resiliency of Cayley graphs generated by transpositions [J]. International Journal of Foundations of Computer Sccience, 2007, 18: 1005-1022.

[1]	裴建峰, 林上为. 极大限制边连通超图的两个充分条件[J]. 运筹学学报, 2019, 23(2): 120-126.
[2]	师海忠, 牛攀峰, 马继勇, 侯斐斐. 互连网络的向量图模型[J]. 运筹学学报, 2011, 15(3): 115-123.