期刊
THEORETICAL COMPUTER SCIENCE
卷 728, 期 -, 页码 1-8出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2018.03.011
关键词
Strong Menger connectivity; Strong Menger edge connectivity; Hypercubes; Folded hypercubes; Connectivity; Fault-tolerance
资金
- National Natural Science Foundation of China [11571044, 61373021]
- Fundamental Research Funds for the Central University of China
Menger's theorem is a characterization of the connectivity in finite graphs in terms of the minimum number of disjoint paths that can be found between any pair of vertices. According to Menger's theorem, a graph G is k-connected if and only if any two vertices of G are connected by at least k internally disjoint paths. Moreover, there are at least K(G) internally disjoint paths and, at most, min{deg(G )(u), deg(G) (v)} internally disjoint paths between any two distinct vertices u, v in G. Motivated by this observation, Oh and Chen (resp., Qiao and Yang) proposed the (fault-tolerant) strong Menger (resp., edge) connectivity as follows. A connected graph G is called strongly Menger (edge) connected if for any two distinct vertices x, y in G, there are min{deg(G) (x), deg(G) (y)} (edge-)disjoint paths between x and y. A graph G is called m-(edge-)fault-tolerant strongly Menger (edge) connected if G - F remains strongly Menger (edge) connected for an arbitrary set F subset of V (G) (resp., F subset of E(G)) with vertical bar F vertical bar <= m. A graph G is called m-conditional (edge-)fault-tolerant strongly Menger (edge) connected if G - F remains strongly Menger (edge) connected for an arbitrary set F subset of V (G) (resp., F subset of E (G)), vertical bar F vertical bar <= m and delta (G-F) >= 2. Qiao and Yang (2017) proved that all n-dimensional folded hypercubes are (2n - 2)-conditional edge-fault-tolerant strongly Menger edge connected for n >= 5. Yang, Zhao and Zhang (2017) showed that all n-dimensional folded hypercubes are (2n - 3)-conditional fault-tolerant strongly Menger connected for n >= 8. In this paper, we improve the result of Qiao and Yang by showing that all n-dimensional folded hypercubes are (3n - 5)-conditional edge-fault-tolerant strongly Menger edge connected for n >= 5. Moreover, we present an example to show that our result is optimal with respect to the maximum tolerated edge faults. In addition, we show that the result of Yang, Zhao and Zhang is optimal by proving that the n-dimensional folded hypercubes are not (2n - 2)-conditional fault-tolerant strongly Menger connected for n >= 8. (C) 2018 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据