Browsing by Author "Chen, Meng-Hung"

Now showing 1 - 2 of 2

Maximally local connectivity and connected components of augmented cubes
(2014-07-20)
Chen, Y-Chuang
;
Chen, Meng-Hung
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
The connectivity of a graph is an important issue in graph theory, and is also one of the most important factors in evaluating the reliability and fault tolerance of a network. It is known that the augmented cube AQ is maximally connected, i.e. (2n - 1)-connected, for n >= 4. By the classic Menger\'s Theorem, every pair of vertices in AQ is connected by 2n - 1 vertex-disjoint paths for n >= 4. A routing with parallel paths can speed up transfers of large amounts of data and increase fault tolerance. Motivated by research on networks with faults, we obtained the result that for any faulty vertex set F c V(AQ) and [F] < 2n - 7 for n >= 4, each pair of non-faulty vertices, denoted by u and v, in AQ F is connected by min{deg(f)(u), deg(f) (v)} vertex-disjoint fault-free paths, where degf(u) and degf(v) are the degree of u and v in AQ(n) - F, respectively. Moreover, we demonstrate that for any faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar < 4n - 9 for n 4, there exists a large connected component with at least 2(n) - vertical bar F vertical bar 1 vertices in AQ F, which improves on the results of Ma et al. (2008) who show this for n >= 6. (C) 2014 Elsevier Inc. All rights reserved.
Maximally Local Connectivity on Augmented Cubes
(2009)
Chen, Y-Chuang
;
Chen, Meng-Hung
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
Connectivity is all important measurement for the fault tolerance in interconnection networks. It is known that the augmented cube AQ(n) is maximally connected, i.e. (2n - 1)-connected, for n >= 4. By the classical Menger\'s Theorem, every pair of vertices in AQ(n) is connected by 2n - 1 vertex-disjoint paths for n >= 4. A routing with parallel paths can speed up transfers of large amounts of data and increase fault tolerance. Motivated by some research works on networks with faults, we have a further result that for any faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar <= 2n - 7 for n >= 4, each pair of non-faulty vertices, denoted by u and v, in AQ(n) - F is connected by min{deg(f)(u), deg(f)(v)} vertex-disjoint fault-free paths, where deg(f)(u) and deg(f)(v) are the degree of u and v in AQ(n) - F, respectively. Moreover, we have another result that for ally faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar <= 4n - 9 for n >= 4, there exists a large connected component with at least 2(n) - vertical bar F vertical bar - 1 vertices in AQ(n) - F. In general, a remaining large fault-free connected component also increases fault tolerance.