Browsing by Author "Kao, Shin-Shin"

Now showing 1 - 11 of 11

Cubic 1-fault-tolerant hamiltonian graphs, Globally 3*-connected graphs, and Super 3-spanning connected graphs
(2013-07-01)
Kao, Shin-Shin
;
Huang, Hua-Min
;
Hsu, Kung-Ming
;
Hsu, Lih-Hsing
;
資訊工程學系
A k-container C(u,v) in a graph G is a set of k internal vertex-disjoint paths between vertices u and v. A k*-container C(u,v) of G is a k-container such that C(u, v) contains all vertices of G. A graph is globally k*-connected if there exists a k*-container C(u, v) between any two distinct vertices u and v. A k-regular graph G is super k-spanning connected if G is i*-connected for 1 <= i <= k. A graph G is 1-fault-tolerant hamiltonian if G F is hamiltonian for any F subset of V boolean OR E and vertical bar F vertical bar = 1. In this paper, we prove that for cubic graphs, every super 3-spanning connected graph is globally 3*-connected and every globally 3*-connected graph is 1-faulttolerant hamiltonian. We present some examples of super 3-spanning connected graphs, some examples of globally 3*-connected graphs that are not super 3-spanning connected graphs, some examples of 1-fault-tolerant hamiltonian graphs that are globally 1*-connected but not globally 3*-connected, and some examples of 1-fault-tolerant hamiltonian that are neither globally 1*-connected nor globally 3*-connected. Furthermore, we prove that there are infinitely many graphs in each such family.
Cubic planar Hamiltonian graphs of various types
(2006-07-06)
Kao, Shin-Shin
;
Hsu, Kung-Ming
;
Hsu, Lih-Hsing
;
應用數學系
;
Department of Applied Mathematics
Let U be the set of cubic planar hamiltonian graphs, A the set of graphs G in U such that G - upsilon is hantiltonian for any vertex upsilon of G, B the set of graphs G in U such that G - e is hamiltonian for any edge e of G, and C the set of graphs G in U such that there is a hamiltonian path between any two different vertices of G. With the inclusion and/or exclusion of the sets A, B, and C, U is divided into eight subsets. In this paper, we prove that there is an infinite number of graphs in each of the eight subsets. (c) 2006 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 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.
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.
Pancyclicity, Panconnectivity, and Panpositionability for General Graphs and Bipartite Graphs
(2012-07-01)
Kao, Shin-Shin
;
Lin, Cheng-Kuan
;
Huang, Hua-Min
;
Hsu, Lih-Hsing
;
資訊工程學系
A graph G is pancyclic if it contains a cycle of every length from 3 to vertical bar V(G)vertical bar inclusive. A graph G is panconnected if there exists a path of length l joining any two different vertices x and y with d(G)(x,y) <= l <= vertical bar V(G)vertical bar - 1, where d(G)(x,y) denotes the distance between x and y in G. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and any integer k with d(G)(x,y) <= k <= vertical bar V(G)vertical bar/2, there exists a hamiltonian cycle C of G with d(C)(x,y) = k, where d(C)(x,y) denotes the distance between x and y in a hamiltonian cycle C of G. It is obvious that panconnected graphs are pancyclic, and panpositionable graphs are pancyclic. The above properties can be studied in bipartite graphs after some modification. A graph H = (V-0 boolean OR V-1, E) is bipartite if V(H) = V-0 boolean OR V-1 and E(H) is a subset of {(u, v) vertical bar u is an element of V-0, v is an element of V-1}. A graph is bipancyclic if it contains a cycle of every even length from 4 to 2 . left perpendicular vertical bar V(H)vertical bar/2right perpendicular inclusive. A graph H is bipanconnected if there exists a path of length 1 joining any two different vertices x and y with d(H)(x,y) <= l <= vertical bar V(H)vertical bar - 1, where d(H)(x, y) denotes the distance between x and y in H and 1 dH(x,y) is even. A hamiltonian graph H is bipanpositionable if for any two different vertices x and y of H and for any integer k with d(H)(x,y) <= k < vertical bar V(H)vertical bar/2, there exists a hamiltonian cycle C of H with d(G)(x,y) = k, where d(G)(x,y) denotes the distance between x and y in a hamiltonian cycle C of H and k - d(H)(x,y) is even. It can be shown that bipanconnected graphs are bipancyclic, and bipanpositionable graphs are bipancyclic. In this paper, we present some examples of pancyclic graphs that are neither panconnected nor panpositionable, some examples of panconnected graphs that are not panpositionable, and some examples of graphs that are panconnected and panpositionable, for nonbipartite graphs. Corresponding examples for bipartite graphs are discussed. The existence of panpositionable (or bipanpositionable, resp.) graphs that are not panconnected (or bipanconnected, resp.) is still an open problem.
"Pancyclicity, Panconnectivity, and Panpositionability for General Graphs and Bipartite Graphs"
(2012-07-01)
Kao, Shin-Shin
;
Lin, Cheng-Kuan
;
Huang, Hua-Min
;
Hsu, Lih-Hsing
;
資訊工程學系
"A graph G is pancyclic if it contains a cycle of every length from 3 to vertical bar V(G)vertical bar inclusive. A graph G is panconnected if there exists a path of length l joining any two different vertices x and y with d(G)(x,y) <= l <= vertical bar V(G)vertical bar - 1, where d(G)(x,y) denotes the distance between x and y in G. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and any integer k with d(G)(x,y) <= k <= vertical bar V(G)vertical bar/2, there exists a hamiltonian cycle C of G with d(C)(x,y) = k, where d(C)(x,y) denotes the distance between x and y in a hamiltonian cycle C of G. It is obvious that panconnected graphs are pancyclic, and panpositionable graphs are pancyclic. The above properties can be studied in bipartite graphs after some modification. A graph H = (V-0 boolean OR V-1, E) is bipartite if V(H) = V-0 boolean OR V-1 and E(H) is a subset of {(u, v) vertical bar u is an element of V-0, v is an element of V-1}. A graph is bipancyclic if it contains a cycle of every even length from 4 to 2 . left perpendicular vertical bar V(H)vertical bar/2right perpendicular inclusive. A graph H is bipanconnected if there exists a path of length 1 joining any two different vertices x and y with d(H)(x,y) <= l <= vertical bar V(H)vertical bar - 1, where d(H)(x, y) denotes the distance between x and y in H and 1 dH(x,y) is even. A hamiltonian graph H is bipanpositionable if for any two different vertices x and y of H and for any integer k with d(H)(x,y) <= k < vertical bar V(H)vertical bar/2, there exists a hamiltonian cycle C of H with d(G)(x,y) = k, where d(G)(x,y) denotes the distance between x and y in a hamiltonian cycle C of H and k - d(H)(x,y) is even. It can be shown that bipanconnected graphs are bipancyclic, and bipanpositionable graphs are bipancyclic. In this paper, we present some examples of pancyclic graphs that are neither panconnected nor panpositionable, some examples of panconnected graphs that are not panpositionable, and some examples of graphs that are panconnected and panpositionable, for nonbipartite graphs. Corresponding examples for bipartite graphs are discussed. The existence of panpositionable (or bipanpositionable, resp.) graphs that are not panconnected (or bipanconnected, resp.) is still an open problem."
Ring embedding in faulty generalized honeycomb torus - GHT(m, n, n/2)
(2010)
Hsu, Li-Yen
;
Ling, Feng-I
;
Kao, Shin-Shin
;
Cho, Hsun-Jung
;
運輸與物流管理系註：原交通所+運管所
The honeycomb torus HT(m) is an attractive architecture for distributed processing applications. For analysing its performance, a symmetric generalized honeycomb torus, GHT(m, n, n/2), with m epsilon 2 and even n epsilon 4, where m+n/2 is even, which is a 3-regular, Hamiltonian bipartite graph, is operated as a platform for combinatorial studies. More specifically, GHT(m, n, n/2) includes GHT(m, 6m, 3m), the isomorphism of the honeycomb torus HT(m). It has been proven that any GHT(m, n, n/2)-e is Hamiltonian for any edge eE(GHT(m, n, n/2)). Moreover, any GHT(m, n, n/2)-F is Hamiltonian for any F={u, v} with uB and vW, where B and W are the bipartition of V(GHT(m, n, n/2)) if and only if n epsilon 6 or m=2, n epsilon 4.
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.