Browsing by Author "Shih, Yuan-Kang"

Now showing 1 - 12 of 12

Conditional fault hamiltonian connectivity of the complete graph
(2009-05-31)
Ho, Tung-Yang
;
Shih, Yuan-Kang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. We denote by B(G) the minimum degree of vertices of G. A graph G is conditional k edge-fault tolerant hamiltonian connected if G - F is hamiltonian connected for every F C E(G) with |F| <= k and S(G - F) >= 3. The conditional edge-fault tolerant hamiltonian connectivity HC(e)(3)(G) is defined as the maximum integer k such that G is k edge-fault tolerant conditional hamiltonian connected if G is hamiltonian connected and is undefined otherwise. Let n >= 4. We use K(n) to denote the complete graph with n vertices. In this paper, we show that HC(e)(3)(K(n)) = 2n - 10 for n is not an element of {4, 5, 8, 10}, HC(e)(3) (K(4)) = 0, HC(e)(3) (K(5)) = 2, HC(e)(3)(K(8)) = 5, and HC(e)(3)(K(10)) = 9. (c) 2009 Elsevier B.V. All rights reserved.
Deformed Honeycomb Tori
(2008)
Shih, Yuan-Kang
;
Kao, Shin-Shin
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
Assume that m, n and s are integers with m >= 2, n >= 4, 0 < s < n and s is of the same parity of m. The generalized honeycomb tori GHT (m, n, s) have been recognized as an attractive architecture to existing torus interconnection networks in parallel and distributed applications. Among the various families of graphs of GHT (m, n, s), numerous studies are devoted to honeycomb hexagonal torus HT(n) due to its nice symmetrical structure. Although each vertex of HT(n) is described by a three-dimensional coordinate (x, y, z), the graph grows uniformly in the three directions. In this article, we propose a new class of graphs extended from HT (n), namely, deformed honeycomb torus DHT (h, l, r). DHT (h, l, r) is defined to allow the graph to grow in the three independent dimensions. We prove that this more general class of graphs still remains a subset of the generalized honeycomb torus. Furthermore, we have a concrete correspondence between any DHT(h, l, r) and the associated GHT (m, n, s).
Hamiltonian connectivity, pancyclicity and 3*-connectivity of matching composition networks
(2008-03-01)
Kao, Shin-Shin
;
Wu, Jui-Chia
;
Shih, Yuan-Kang
;
資訊工程學系
;
Department of Computer Science
In this paper, we discuss many properties of graphs of Matching Composition Networks (MCN) [16]. A graph in MCN is obtained front the disjoint union of two graphs Go and G, by adding a pet-feet matching between V(G(0)) and V(G(1)). We prove that any graph in MCN preserves the hamiltonian connectivity or hamiltonian laceability, and pancyclicity of G(0) and G(1) under simple conditions. In addition, if there exist three internally vertex-disjoint paths between any pair of distinct vertices in G(i) for i is an element of {0, 11, then so it is the case in any graph in MCN. Since MCN includes many well-known interconnection networks as special cases, such as the Hypercube Q(n), the Crossed cube CQ(n), the Twisted cube TQ(n), the Mobius cube MQ(n), and the Hypbercube-like graphs HLn, our results apply to all of the above-mentioned networks.
Mutually independent bipanconnected property of hypercube
(2010-12-15)
Shih, Yuan-Kang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
A graph is denoted by G with the vertex set V(G) and the edge set E(G). A path P = < v(0), v(1),..., v(m)> is a sequence of adjacent vertices. Two paths with equal length P(1) = < u(1), u(2),..., u(m)> and P(2) = < v(1), v(2),..., v(m)> from a to b are independent if u(1) = v(1) = a, u(m) = v(m) = b, and u(i) not equal v(i) for 2 <= i 6 <= m - 1. Paths with equal length {P(i)}(i-1)(n) from a to b are mutually independent if they are pairwisely independent. Let u and v be two distinct vertices of a bipartite graph G, and let l be a positive integer length, d(G)(u, v) <= l <= vertical bar V(G) - 1 vertical bar with (l - d(G)(u, v)) being even. We say that the pair of vertices u, v is ( m, l)- mutually independent bipanconnected if there exist m mutually independent paths {P(i)(l)}(i-1)(m) with length l from u to v. In this paper, we explore yet another strong property of the hypercubes. We prove that every pair of vertices u and v in the n-dimensional hypercube, with d(Qn) (u, v) >= n - 1, is (n - 1,l)-mutually independent bipanconnected for every l; d(Qn) (u, v) <= l <= vertical bar V(Q(n))-1 vertical bar with (l - d(Qn) (u, v)) being even. As for d(Qn) (u, v) <= n - 2, it is also (n - 1,l)-mutually independent bipanconnected if l >= d(Qn) (u, v) + 2, and and is only (l,l)-mutually independent bipanconnected if l = d(Qn)(u, v). (C) 2010 Elsevier Inc. All rights reserved.
Mutually independent Hamiltonian cycles in dual-cubes
(2010-11-01)
Shih, Yuan-Kang
;
Chuang, Hui-Chun
;
Kao, Shin-Shin
;
Tan, Jimmy J. M.
;
資訊工程學系
The hypercube family Q(n) is one of the most well-known interconnection networks in parallel computers. With Q(n) , dual-cube networks, denoted by DC(n) , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DC(n)'s are shown to be superior to Q(n)'s in many aspects. In this article, we will prove that the n-dimensional dual-cube DC(n) contains n+1 mutually independent Hamiltonian cycles for n >= 2. More specifically, let upsilon(i) is an element of V(DC (n) ) for 0 <= i <= |V(DC(n))|-1 and let (upsilon(0,) upsilon(1,.....,) upsilon broken vertical bar v(DC(n))broken vertical bar-1, upsilon(0)) be a Hamiltonian cycle of DC(n) . We prove that DC(n) contains n+1 Hamiltonian cycles of the form (upsilon(0,) upsilon(k)(1), .....,upsilon(k)vertical bar v (DC(n))vertical bar-1, upsilon(0)) for 0 <= k <= n, in which v(i)(k) not equal v(i)(k') whenever k not equal k'. The result is optimal since each vertex of DC(n) has only n+1 neighbors.
Mutually independent Hamiltonian cycles in dual-cubes
(2010-11-01)
Shih, Yuan-Kang
;
Chuang, Hui-Chun
;
Kao, Shin-Shin
;
Tan, Jimmy J. M.
;
資訊工程學系
The hypercube family Q(n) is one of the most well-known interconnection networks in parallel computers. With Q(n) , dual-cube networks, denoted by DC(n) , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DC(n)'s are shown to be superior to Q(n)'s in many aspects. In this article, we will prove that the n-dimensional dual-cube DC(n) contains n+1 mutually independent Hamiltonian cycles for n >= 2. More specifically, let upsilon(i) is an element of V(DC (n) ) for 0 <= i <= |V(DC(n))|-1 and let (upsilon(0,) upsilon(1,.....,) upsilon broken vertical bar v(DC(n))broken vertical bar-1, upsilon(0)) be a Hamiltonian cycle of DC(n) . We prove that DC(n) contains n+1 Hamiltonian cycles of the form (upsilon(0,) upsilon(k)(1), .....,upsilon(k)vertical bar v (DC(n))vertical bar-1, upsilon(0)) for 0 <= k <= n, in which v(i)(k) not equal v(i)(k') whenever k not equal k'. The result is optimal since each vertex of DC(n) has only n+1 neighbors.
Mutually Independent Hamiltonian Cycles in Some Graphs
(2012-07-01)
Lin, Cheng-Kuan
;
Shih, Yuan-Kang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
Let G = (V, E) be a hamiltonian graph. A hamiltonian cycle C of G is described as < v(1), v(2) ,..., v(n)(G), v(1)> to emphasize the order of vertices in C. Thus, v(1) is the beginning vertex and v(i) is the i-th vertex in C. Two hamiltonian cycles of G beginning at u, C-1 = < u(1), u(2),..., u(n(G)), u(1)> and C-2 = < v(1), v(2), ..., v(n(G),) v(1)) of G are independent if u(1) = v(1) = u, and u(i) not equal v(i) for every 2 <= i <= n(G). A set of hamiltonian cycles {C-1, C-2,..., C-k} of G are mutually independent if they are pairwise independent. The mutually independent hamiltonianicity of graph G, IHC(G), is the maximum integer k such that for any vertex u there are k-mutually independent hamiltonian cycles of G beginning at u. In this paper, we prove that IHC(C) <= delta(G) for any hamiltonian graph and IHC(G) >= 2 delta(G) - n(G) + 1 if delta(G) >= n(G)/2. Moreover, we present some graphs that meet the bound mentioned above.
One-to-one disjoint path covers on k-ary n-cubes
(2011-08-12)
Shih, Yuan-Kang
;
Kao, Shin-Shin
;
資訊工程學系
;
Department of Computer Science
The k-ary n-cube, Q(n)(k) is one of the most popular interconnection networks. Let n >= 2 and k >= 3. It is known that Q(n)(k) is a nonbipartite (resp. bipartite) graph when k is odd (resp. even). In this paper, we prove that there exist r vertex disjoint paths {P(i) vertical bar 0 <= i <= r - 1} between any two distinct vertices u and v of Q(n)(k) when k is odd, and there exist r vertex disjoint paths {R(i) vertical bar 0 <= i <= r - 1} between any pair of vertices to and b from different partite sets of Q(n)(k) when k is even, such that boolean OR(r-1)(i=0) P(i) or boolean OR(r-1)(i=0) R(i) covers all vertices of Q(n)(k) for 1 <= r <= 2n. In other words, we construct the one-to-one r-disjoint path cover of Q(n)(k) for any r with 1 <= r <= 2n. The result is optimal since any vertex in Q(n)(k) has exactly 2n neighbors. (C) 2011 Elsevier B.V. All rights reserved.
The bipanpositionable bipancyclic property of the hypercube
(2009-11-01)
Shih, Yuan-Kang
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to vertical bar V(G)vertical bar inclusive. A hamiltonian bipartite graph G is bipanpositionable if, for any two different vertices x and y, there exists a hamiltonian cycle C of G such that d(c)(x, y) = k for any integer k with d(G)(x, y) <= k <= vertical bar V(G)vertical bar/2 and (k - d(G)(x, y)) being even. A bipartite graph G is k-cycle bipanpositionable if, for any two different vertices x and y, there exists a cycle of G with d(C)(x, y) = l and vertical bar V(C)vertical bar = k for any integer l with d(G)(x, y) <= l <= k/2 and (l - d(G)(x, y)) being even. A bipartite graph G is bipanpositionable bipancyclic if G is k-cycle bipanpositionable for every even integer k, 4 <= k <= vertical bar V(G)vertical bar. We prove that the hypercube Q(n) is bipanpositionable bipancyclic for n >= 2. (C) 2009 Elsevier Ltd. All rights reserved.
The construction of mutually independent Hamiltonian cycles in bubble-sort graphs
(2010)
Shih, Yuan-Kang
;
Lin, Cheng-Kuan
;
Hsu, D. Frank
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
A Hamiltonian cycle C=< u(1), u(2), ..., u(n(G)), u(1) > with n(G)=number of vertices of G, is a cycle C(u(1); G), where u(1) is the beginning and ending vertex and u(i) is the ith vertex in C and u(i)not equal u(j) for any i not equal j, 1 <= i, j <= n(G). A set of Hamiltonian cycles {C(1), C(2), ..., C(K)} of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B(n))=n-1 if n >= 4, where B(n) is the n-dimensional bubble-sort graph.
The Mutually Independent Bipanconnected Property for Hypercube
(2009)
Shih, Yuan-Kang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
A graph is denoted by G with the vertex set V(G) and the edge set E(G). A path P = < vo,vi, ... ,v(m)> is a sequence of adjacent vertices. Two paths with equal length Pi = < u(1), u(2), ... ,U(m)> and P(2) = (v(0), v(1), ... , v(m)) from a to b are independent if u(1) = v1 = a, u(m) = v(m) = b, and u(i) not equal v(i). for 2 <= i <= m - 1. Paths with equal length {Pi}(i=1)(n) from a to b are mutually independent if they are pairwisely independent. Let u and v be two distinct vertices of a bipartite graph G, and let 1 be a positive integer length, d(G)(u, v) <= 1 <= |V(G) - 1| with (l - dc(u, v)) being even. We say that the pair of vertices u, v is (m,1)-mutually independent bipanconnected if there exist m mutually independent paths {P(i)(l)}(i=1)(m) with length l from u to v. In this paper, we explore yet another strong property of the hypercubes. We prove that every pair of vertices u and v in the n-dimensional hypercube, with d(Qn)(u,v) >= n - 1, is (n - 1, l)-mutually independent bipanconnected for every l, d(Qn)(u, v) <= 1 <= |V(Q(n))-1| with (l - d(Qn)(u, v)) being even. As for d(Qn)(u,v)<= n - 2, it is also (n - 1, l)-mutually independent bipanconnected if l >= d(Qn) (u, v) + 2, and is only (l, l)-mutually independent bipanconnected if l= d(Qn)(u,v).
Vertex-bipancyclicity of the generalized honeycomb tori
(2008-12-01)
Shih, Yuan-Kang
;
Wu, Yi-Chien
;
Kao, Shin-Shin
;
Tan, Jimmy J. M.
;
資訊工程學系
Assume that m, n and s are integers with m >= 2, n >= 4, 0 <= s < n and s is of the same parity of m. The generalized honeycomb tori GHT(m, n, s) have been recognized as an attractive architecture to existing torus interconnection networks in parallel and distributed applications. A bipartite graph G is bipancyclic if it contains a cycle of every even length from 4 to vertical bar V(G)vertical bar inclusive. G is vertex-bipancyclic if for any vertex nu is an element of V(G), there exists a cycle of every even length from 4 to vertical bar V(G)vertical bar that passes nu. A bipartite graph G is called k-vertex-bipancyclic if every vertex lies on a cycle of every even length from k to vertical bar V(G)vertical bar. In this article, we prove that GHT(m, n, s) is 6-bipancyclic, and is bipancyclic for some special cases. Since GHT(m. n. s) is vertex-transitive, the result implies that any vertex of GHT(m. n. s) lies on a cycle of length l, where l >= 6 and is even. Besides, GHT(m, n, s) is vertex-bipancyclic in some special cases. The result is optimal in the sense that the absence of cycles of certain lengths on some GHT(m, n. s)'s is inevitable due to their hexagonal structure. (C) 2008 Elsevier Ltd. All rights reserved.