期刊
DISCRETE APPLIED MATHEMATICS
卷 294, 期 -, 页码 108-114出版社
ELSEVIER
DOI: 10.1016/j.dam.2021.01.030
关键词
Edge-disjoint path; Strong Menger edge-connectivity; Edge-fault- tolerance; Extra edge-connectivity; Augmented cube
资金
- Shandong Provincial Natural Science Foundation, China [ZR2017MA018, ZR2017MF071]
- SDIBT, China [BS201616]
- National Natural Science Foundation of China [61672321]
This article investigates edge-disjoint paths in augmented cubes with faulty edges, proving some important results and introducing the concept of extra edge-connectivity.
Motivated by evaluating the reliability and fault tolerance of a network, we consider edge-disjoint paths in augmented cubes with faulty edges. We show that for any faulty edge set F subset of E(AQ(n)) and delta (AQ(n) - F) >= 2, if vertical bar F vertical bar <= 4n - 8 for n >= 4, there are min{deg(AQn - F)(u), deg(AQn - F)(nu)} edge-disjoint paths connected any two vertices u and nu in AQ(n) - F, where deg(AQn - F)(u) and deg(AQn - F)(nu) are the degree of vertices u and nu in AQ(n) - F, respectively. This result is optimal with respect to the maximum number of faulty edges. Simultaneously, we determine lambda(1)(AQ(n)) for n >= 2, and lambda(2)(AQ(n)) for n >= 4, where lambda(g)(AQ(n)) is the g-extra edge-connectivity of AQ(n). Given a graph G and a non-negative integer g, the g-extra edge-connectivity of G, denoted lambda(g)(G), is the minimum cardinality of a set of edges in G, if it exists, whose deletion disconnects G and leaves each remaining component with more than g vertices. (C) 2021 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据