4.5 Article

Packing internally disjoint Steiner trees to compute the κ3-connectivity in augmented cubes

期刊

出版社

ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jpdc.2021.04.004

关键词

Augmented cubes; Connectivity; Interconnection networks; Internally disjoint Steiner trees; Generalized connectivity

资金

  1. National Natural Science Foundation of China [11971054, 11731002]
  2. Ministry of Science and Technology of Taiwan [07-2221-E-141-001-MY3]

向作者/读者索取更多资源

This paper focuses on constructing internally disjoint S-trees with |S| = 3 in the n-dimensional augmented cube A Q(n), and completely determines the kappa(3)-connectivity of A Q(n).
Given a connected graph G and S subset of V(G) with vertical bar S vertical bar >= 2, a tree T in G is called an S-Steiner tree (or S-tree for short) if S subset of V (T). Two S-trees T-1 and T-2 are internally disjoint if E(T-1) boolean AND E(T-2) = empty set and V (T-1) boolean AND V (T-2) = S. The packing number of internally disjoint S-trees, denoted as kappa(G) (S), is the maximum size of a set of internally disjoint S-trees in G. For an integer kappa >= 2, the generalized k-connectivity (abbr. kappa(kappa)-connectivity) of a graph G is defined as kappa(kappa) (G) = min{kappa(G) (S) vertical bar S subset of V (G) and vertical bar S vertical bar = kappa}. The n-dimensional augmented cube, denoted as A Q(n), is an important variant of the hypercube that possesses several desired topology properties such as diverse embedding schemes in applications of parallel computing. In this paper, we focus on the study of constructing internally disjoint S-trees with vertical bar S vertical bar = 3 in A Q(n). As a result, we completely determine the kappa(3)-connectivity of A Q(n) as follows: kappa(3) (A Q(4)) = 5 and kappa(3) (A Q(n)) = 2n - 2 for n = 3 or n >= 5. (C) 2021 Elsevier Inc. All rights reserved.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.5
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据