Browsing by Author "Li, TK"

Now showing 1 - 7 of 7

Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes
(2003-07-31)
Li, TK
;
Tsai, CH
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to I V(G) I inclusive. It has been shown that Q(n) is bipancyclic if and only if n greater than or equal to 2. In this paper, we improve this result by showing that every edge of Q(n) - E' lies on a cycle of every even length from 4 to V(G) inclusive where E' is a subset of E(Q(n)) with E' less than or equal to n - 2. The result is proved to be optimal. To get this result, we also prove that there exists a path of length I joining any two different vertices x and y of Qn when h (x, y) less than or equal to l less than or equal to V(G) - 1 and l - h (x, y) is even where It (x, y) is the Hamming distance between x and y. (C) 2003 Elsevier Science B.V. All rights reserved.
Fault hamiltonicity and fault hamiltonian connectivity of the arrangement graphs
(2004-01-01)
Hsu, HC
;
Li, TK
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
The arrangement graph A(n,k) is a generalization of the star graph. There are some results concerning fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graph. However, these results are restricted in some particular cases and, thus, are less completed. In this paper, we improve these results and obtain a stronger and simpler statement. Let n - k greater than or equal to 2 and F subset of or equal to V(A(n,k)) boolean OR E(A(n,k)). We prove that A(n,k) - F is Hamiltonian if F less than or equal to k(n - k) - 2 and A(n,k) - F is Hamiltonian connected if F less than or equal to k(n - k) - 3. These results are optimal.
Fault-tolerant cycle-embedding of crossed cubes
(2003-11-30)
Yang, MC
;
Li, TK
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
The crossed cube CQ(n) introduced by Efe has many properties similar to those of the popular hypercube. However, the diameter of CQ(n) is about one half of that of the hypercube. Failures of links and nodes in an interconnection network are inevitable. Hence, in this paper, we consider the hybrid fault-tolerant capability of the crossed cube. Letting f(e) and f(v) be the numbers of faulty edges and vertices in CQ(n), we show that a cycle of length 1, for any 4 less than or equal to l less than or equal to V(CQ(n)) - f(v) can be embedded into a wounded crossed cube as long as the total number of faults (f(v) +f(e)) is no more than n - 2, and we say that CQ(n) is (n - 2)-fault-tolerant pancyclic. This result is optimal in the sense that if there are n - 1 faults, there is no guarantee of having a cycle of a certain length in it. (C) 2003 Published by Elsevier B.V.
Fault-tolerant pancyclicity of the Mobius cubes
(2005-01-01)
Yang, MC
;
Li, TK
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
The Mobius cube MQ(n) proposed by Cull et al. is an alternative to the popular hypercube network. Recently, MQ(n) was shown to be pancyclic, i.e., cycles of any,lengths at least four can be embedded into it. Due to the importance of the fault tolerance in the parallel processing area, in this paper, we study an injured MQ(n) with mixed node and link faults. We show that it is (n - 2)-fault-tolerant pancyclic for n greater than or equal to 3, that is, an injured n-dimensional MQ(n) is still pancyclic with up to (n - 2) faults. Furthermore, our result is optimal.
Hyper hamiltonian laceability on edge fault star graph
(2004-09-03)
Li, TK
;
Tar, JJM
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
The star graph posses many nice topological properties. Edge fault tolerance is an important issue for a network since the edges in the network may fail sometimes. In this paper, we show that the n-dimensional star graph is (n - 3)-edge fault tolerant hamiltonian laceable, (n - 3)-edge fault tolerant strongly hamiltonian laceable, and (n - 4)-edge fault tolerant hyper hamiltonian laceable. All these results are optimal in a sense described in this paper. (C) 2003 Elsevier Inc. All rights reserved.
On embed-ding cycles into faulty twisted cubes
(2006-03-22)
Yang, MC
;
Li, TK
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
The twisted cube TQ(n) is an alternative to the popular hypercube network. Recently, some interesting properties of TQ(n) were investigated. In this paper, we study the pancycle problem on faulty twisted cubes. Let f(e) and f(v) be the numbers of faulty edges and faulty vertices in TQ(n), respectively. We show that, with f(e) + f(v) <= n - 2, a faulty TQ(n) still contains a cycle of length l for every 4 <= l < V(TQ(n)) - f(v) and odd integer n >= 3. (C) 2005 Elsevier Inc. All rights reserved.
The shuffle-cubes and their generalization
(2001-01-31)
Li, TK
;
Tan, JJM
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
In this paper, we first present a new variation of hypercubes, denoted by SQ(n) .SQ(n) is obtained from Q(n) by changing some links. Sa, is also an n-regular n-connected graph but of diameter about n/4. Then, we present a generalization of Se,. For any positive integer g, we can construct an n-dimensional generalized shuffle-cube with 2(n) vertices which is n-regular and n-connected. However its diameter can be about n/g if we consider g as a constant. (C) 2001 Elsevier Science B.V. All rights reserved.