The generalized 4-connectivity of hypercubes

详细信息    查看全文

• 作者：Shangwei Lin ; ^{shangweilin@sxu.edu.cn} ; Qianhua Zhang
• 关键词：Hypercube ; Fault-tolerance ; Generalized connectivity ; Tree
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：31 March 2017
• 年：2017
• 卷：220
• 期：Complete
• 页码：60-67
• 全文大小：659 K
• 卷排序：220

文摘

The connectivity and the spanning tree packing number of a graph are two important measurements for the fault-tolerance of a network. The generalized connectivity is a common generalization of the classical connectivity and spanning tree packing number. In this paper, we show that the generalized 4-connectivity of the nn-dimensional hypercube QnQn is (n−1)(n−1), that is, for any four vertices in QnQn, there exist (n−1)(n−1) internally disjoint trees connecting them in QnQn.