完全对换网络的嵌入连通度

丁秀艳; 艾尔肯·吾买尔

doi:10.13568/j.cnki.651094.2019.01.005

您当前的位置：

首页 >

文章列表页 >

完全对换网络的嵌入连通度

更新时间：2026-01-21

- 完全对换网络的嵌入连通度
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 36, Issue 1, Pages: 34-38(2019)
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：10.13568/j.cnki.651094.2019.01.005
  CLC： O157.5
- Published：2019
- 稿件说明：
移动端阅览
[1]丁秀艳,艾尔肯·吾买尔.完全对换网络的嵌入连通度[J],2019,36(01):34-38.
[1]丁秀艳,艾尔肯·吾买尔.完全对换网络的嵌入连通度[J],2019,36(01):34-38. DOI： 10.13568/j.cnki.651094.2019.01.005.

DOI：10.13568/j.cnki.651094.2019.01.005.

摘要

一个n维的递归交互网络Gn的一个点(边)子集称为Gn的一个h-嵌入点(边)割(如果这样的子集存在的话)

使得删去这个点(边)子集后得到的图是不连通的且每个点都在一个未损坏的h-维子网络Gh中.图Gn的h-嵌入(边)连通度

记为ζh(Gn)(ηh(Gn))

定义为Gn的最小h-嵌入点(边)割的基数.完全对换网络CTn是网络设计中一类重要的Cayley图.在本文中

我们确定了完全对换网络的h-嵌入(边)连通度:ζh(CTn)=h!/2[n(n-1)-h(h-1)]

其中2≤h≤n-2

ηh(CTn)=h!/2[n(n-1)-h(h-1)]

其中2≤h≤n-1.

Abstract

For an n-dimensional recursive interconnection network Gn

the h-embedded connectivity of Gn

denoted by ζh(Gn)(resp. the h-embedded edge-connectivity of Gn

denoted by ηh(Gn))

is the cardinality of a minimum subset of vertices(resp. edges)

if any

whose deletion disconnects Gn and each vertex of remaining components is contained in an undamaged h-dimensional subnetwork Gh. Complete-transposition graphs CTn are a class of important Cayley graphs in network design. In this paper

we determine ζh andηh for complete-transposition graphs: ζh(CTn) =h!/2[n(n-1)-h(h-1)] for 2 ≤ h ≤ n-2

and ηh(CTn) =h!/2[n(n-1)-h(h-1)] for 2 ≤ h ≤ n-1.

关键词

Keywords

references

Bondy J, Murty U. Graph Theory with Applications[M].New York:Springer, 2008.

Harary F. Conditional connectivity[J]. Networks, 1983, 13(3):347-357.

Li X, Dong Q, Yan Z. Embedded connectivity of recursive networks[J]. Theoret Comput Sci, 2016, 653:79-86.

Yang Y, Wang S, Li J. Conditional connectivity of recursive interconnection networks respect to embedding restriction[J].Inf Sci, 2014, 279(279):273-279.

Chen L, Liu F, Meng J. The connectivity of hypergraphs[J]. J Xinjiang Univ(Natural Sci Edit), 2017,34(1):1-6.

Leighton F. Introduction to parallel algorithms and architectures:array, trees, hypercubes[M]. San Francisco:Morgan Kaufmann, 2014.

Lakshmivarahan S, Jwo J S, Dhall S. Symmetry in interconnection networks based on Cayley graphs of permutation groups:A survey[J]. Parallel Comput, 1993, 19(4):361-407.

Akers S, Krishnamurthy B. A group-theoretic model for symmetric interconnection networks.[J]. IEEE Trans Comput,1989, 38(4):555-566.

Fujita S. Polynomial time algorithm for constructing vertex-disjoint paths in transposition graphs[J]. Networks, 2010,56(2):149-157.

Meng J, Wang S. Hamiltonian property of two class of Cayley graphs[J]. J Xinjiang Univ(Natural Sci Edit), 1994, 11(2):19-21.

Latifi S, Srimani P. Transposition networks as a class of fault-tolerant robust networks[J]. IEEE Trans Comput, 1996,45(2):230-238.

Suzuki Y, Kaneko K, Nakamori M. Node-disjoint paths algorithm in a transposition graph[M].Oxford:Oxford Univ, 2006.

Qiao H, Elkin V. The laceability of the transposition network[J]. J Xinjiang Univ(Natural Sci Edit), 2017,34(1):44-47.

Shi H, Wang G, Ma J. One variety conjectures of complete-transposition network[J]. Comput Sci, 2012:404-407.

Wang G, Shi H, Hou F. Some conditional vertex connectivities of complete-transposition graphs[J]. Inf Sci, 2015, 295:536-543.

Wang G, Shi H. The restricted connectivity of complete commutation networks[J].Or Transact, 2013, 17(3):57-64.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

由对换树生成的凯莱图的3-额外连通度(英文)

Related Author

李恒哲

孟吉翔

杨卫华

Related Institution

厦门大学数学与系统科学学院

⁰