在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2015, Vol. 32 ›› Issue (1): 107-115.doi: 10.3969/j.issn.1005-3085.2015.01.011

• • 上一篇    下一篇

一类新的互连网络：三角塔网络

师海忠,   白亚兰,   王国亮,   胡艳红   

  1. 西北师范大学数学与统计学院，兰州 730070
  • 收稿日期:2014-02-24 接受日期:2014-10-09 出版日期:2015-02-15 发布日期:2015-04-15
  • 基金资助:
    甘肃省自然科学基金 (ZS991-A25-017-G).

Triangle Tower Network: a New Class of Interconnection Network

SHI Hai-zhong,   BAI Ya-lan,   WANG Guo-liang,   HU Yan-hong   

  1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070
  • Received:2014-02-24 Accepted:2014-10-09 Online:2015-02-15 Published:2015-04-15
  • Supported by:
    The Natural Science Foundation of Gansu Province (ZS991-A25-017-G).

PDF (PC)

14

摘要： 本文提出并分析了一种新的互连网络---三角塔网络．当$n>4$或$n=4$时，它是极大连通的，紧超连通的，即三角塔网络的连通度$\kappa(TT_{n})$是$2n-3$．星网络是三角塔网络的子网络，故而三角塔网络除了继承星网络的很多优良性质(例如：点对称性、连通性、点可迁性等)，还说明$S_{n}$能以膨胀数1嵌入$TT_{n}$．当三角塔网络和超立方体与冒泡排序网络有近乎相同的顶点数时，三角塔网络的直径和连通度与超立方体与冒泡排序网络的直径和连通度相比直径更小、连通度更大．本文给出了三角塔网络的直径和平均距离，并提出了关于三角塔网络Hamilton性的一簇猜想，并且证明这个猜想对于$n=3,4$以及$n=5,6,~k=1,2$时是正确的．

关键词: 互连网络, Cayley图, 三角塔网络, 直径, Hamilton性

Abstract:

In this paper, we propose and analyze a new interconnection network called triangle tower graph/network. It is maximally connected and tightly super-connected, for $n>4$ or $n=4$, i.e. the connectivity $\kappa(TT_{n})$ of $TT_{n}$ is $2n-3$. The star graph is a specific subgraph of the proposed triangle tower graph. Therefore, the triangle tower graph not only inherits many good capabilities possessed by the star graph (e.g., vertex symmetry, connectivity, vertex transition, etc.), but also shows that $S_{n}$ can be embedded into $TT_{n}$ with digit 1. The proposed triangle tower graph is superior to the traditional hypercube and bubble-sort graph with respect to diameter, connectivity and conditional vertex connectivity as that these three graphs have approximately similar numbers of vertices. The diameter and average distance are presented for the proposed network. We also propose one variety conjectures on Hamiltonicity of triangle tower graph and prove conjectures are true for $n=3,4$ and $n=5,6,~k=1,2$.

Key words: interconnection networks, Cayley graphs, triangle tower graph, diameter, Hamilton cycles

中图分类号: