期刊
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
卷 154, 期 -, 页码 42-53出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jpdc.2021.04.004
关键词
Augmented cubes; Connectivity; Interconnection networks; Internally disjoint Steiner trees; Generalized connectivity
资金
- National Natural Science Foundation of China [11971054, 11731002]
- 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据