期刊
THEORETICAL COMPUTER SCIENCE
卷 627, 期 -, 页码 36-53出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2016.02.024
关键词
Conditional diagnosability; Comparison model; Extra connectivity; Symmetric graph; Cayley graph; Max-min problem
资金
- NNSF of China [11371052, 11271012, 61272008, 11571044]
The conditional diagnosability and the 2-extra connectivity are two important parameters to measure ability of diagnosing faulty processors and fault-tolerance in a multiprocessor system. The conditional diagnosability t(c)(G) of G is the maximum number t for which G is conditionally t-diagnosable under the comparison model, while the 2-extra connectivity kappa(2)(G) of a graph G is the minimum number k for which there is a vertex-cut F with vertical bar F vertical bar = k such that every component of G - F has at least 3 vertices. A quite natural problem is what is the relationship between the maximum and the minimum problem? This paper partially answers this problem by proving t(c)(G)=kappa(2)(G) for a regular graph G with some acceptable conditions. As applications, the conditional diagnosability and the 2-extra connectivity are determined for some well-known classes of vertex-transitive graphs, including, star graphs, (n, k)-star graphs, alternating group networks, (n, k)-arrangement graphs, alternating group graphs, Cayley graphs obtained from transposition generating trees, bubble-sort graphs, k-ary n-cube networks, dual-cubes, pancake graphs and hierarchical hypercubes as well. Furthermore, many known results about these networks are obtained directly. (C) 2016 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据