Browsing by Author "Hsu, Lih-Hsing"

Now showing 1 - 20 of 60

4-ordered-Hamiltonian problems of the generalized Petersen graph GP(n, 4)
(2013-02-01)
Hung, Chun-Nan
;
Lu, David
;
Jia, Randy
;
Lin, Cheng-Kuan
;
Liptak, Laszlo
A graph G is k-ordered if for every sequence of k distinct vertices of G, there exists a cycle in G containing these k vertices in the specified order. It is k-ordered-Hamiltonian if, in addition, the required cycle is a Hamiltonian cycle in G. The question of the existence of an infinite class of 3-regular 4-ordered-Hamiltonian graphs was posed in Ng and Schultz in 1997 [2]. At the time, the only known examples of such graphs were K-4 and K-3,K-3. Some progress was made by Meszaros in 2008 [21] when the Petersen graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered-Hamiltonian; moreover, an infinite class of 3-regular 4-ordered graphs was found. In 2010, a subclass of the generalized Petersen graphs was shown to be 4-ordered in Hsu et al. [9], with an infinite subset of this subclass being 4-ordered-Hamiltonian, thus answering the open question. However, these graphs are bipartite. In this paper we extend the result to another subclass of the generalized Petersen graphs. In particular, we find the first class of infinite non-bipartite graphs that are both 4-ordered-Hamiltonian and 4-ordered-Hamiltonian-connected, which can be seen as a solution to an extension of the question posted in Ng and Schultz in 1997 [2]. (A graph G is k-ordered-Hamiltonian-connected if for every sequence of k distinct vertices a(1), a(2),..., a(k) of G, there exists a Hamiltonian path in G from a(1) to a(k) where these k vertices appear in the specified order.) (C) 2012 Elsevier Ltd. All rights reserved.
A family of Hamiltonian and Hamiltonian connected graphs with fault tolerance
(2010-11-01)
Chen, Y-Chuang
;
Huang, Yong-Zen
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
資訊工程學系
Processor (vertex) faults and link (edge) faults may happen when a network is used, and it is meaningful to consider networks (graphs) with faulty processors and/or links. A k-regular Hamiltonian and Hamiltonian connected graph G is optimal fault-tolerant Hamiltonian and Hamiltonian connected if G remains Hamiltonian after removing at most k-2 vertices and/or edges and remains Hamiltonian connected after removing at most k-3 vertices and/or edges. In this paper, we investigate in constructing optimal fault-tolerant Hamiltonian and optimal fault-tolerant Hamiltonian connected graphs. Therefore, some of the generalized hypercubes, twisted-cubes, crossed-cubes, and Mobius cubes are optimal fault-tolerant Hamiltonian and optimal fault-tolerant Hamiltonian connected.
A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
(2009-04-01)
Kueng, Tz-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
In the paper "Fault-free Mutually Independent Hamiltonian Cycles in Hypercubes with Faulty Edges" (J. Comb. Optim. 13:153-162, 2007), the authors claimed that an n-dimensional hypercube can be embedded with (n-1-f)-mutually independent Hamiltonian cycles when fa parts per thousand currency signn-2 faulty edges may occur accidentally. However, there are two mistakes in their proof. In this paper, we give examples to explain why the proof is deficient. Then we present a correct proof.
A recursively construction scheme for super fault-tolerant hamiltonian graphs
(2006-06-15)
Chen, Y-Chuang
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
For the interconnection network topology, it is usually represented by a graph. When a network is used. processors and/or links faults may happen. Thus, it is meaningful to consider faulty networks, We consider k-regular graphs in this paper. We define a k-regular hamiltonian and hamiltonian connected graph G is super fault-tolerant hamiltonian if G remains hamiltonian after removing at most k - 2 vertices and/or edges and remains hamiltonian connected after removing at most k - 3 vertices and/or edges. A Super fault-tolerant hamiltonian graph has a certain optimal flavor with respect to the fault tolerant hamiltonicity and fault-tolerant hamiltonian connectivity. The aim of this paper is to investigate a construction scheme to construct various super fault-tolerant hamiltonian graphs. Along the way. the recursire circulant graph is a special case of our construction scheme. and the super fault-tolerant hamiltonian property of recursive circulant graph is obtained. (c) 2005 Elsevier Inc. All rights reserved.
Component connectivity of the hypercubes
(2012)
Hsu, Lih-Hsing
;
Cheng, Eddie
;
Liptak, Laszlo
;
Tan, Jimmy J. M.
;
Lin, Cheng-Kuan
The r-component connectivity kappa(r)(G) of the non- complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. So, kappa(2) is the usual connectivity. In this paper, we determine the r-component connectivity of the hypercube Q(n) for r = 2, 3, ..., n + 1, and we classify all the corresponding optimal solutions.
Conditional diagnosability of hypercubes under the comparison diagnosis model
(2009-02-01)
Hsu, Guo-Huang
;
Chiang, Chieh-Feng
;
Shih, Lun-Min
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
Processor fault diagnosis plays an important role in multiprocessor systems for reliable computing, and the diagnosability of many well-known networks has been explored. Lai et al. proposed a novel measure of diagnosability, called conditional diagnosability, by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. We make a contribution to the evaluation of diagnosability for hypercube networks under the comparison model and prove that the conditional diagnosability of n-dimensional Hypercube Q(n) is 3(n - 2) + 1 for n >= 5. The conditional diagnosability of Q. is about three times larger than the classical diagnosability of Q(n). (C) 2008 Elsevier B.V. All rights reserved.
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.
Conditional Fault Hamiltonicity of the Star Graph
(2014-01-01)
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
Cheng, Eddie
;
Liptak, Laszlo
Fault tolerance is an important property on network performance. A graph G is k-edge-fault conditional hamiltonian if G - F is hamiltonian for every F subset of E(G) with vertical bar F vertical bar <= k and delta(G - F) >= 2. In this paper we show that for n >= 4 the n-dimensional star graph S-n is (3n - 10)-edge-fault conditional hamiltonian.
CONDITIONAL MATCHING PRECLUSION FOR THE STAR GRAPHS
(2015-04-01)
Cheng, Eddie
;
Liptak, Laszlo
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
Lin, Cheng-Kuan
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those incident to a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those incident to a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number and classify all optimal sets for the star graphs, one of the most popular interconnection networks.
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).
Disjoint cycles in hypercubes with prescribed vertices in each cycle
(2013-12-01)
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
Kung, Tzu-Liang
;
資訊工程學系
A graph G is spanning r-cyclable of order t if for any r nonempty mutually disjoint vertex subsets A(1), A(2) ,..., A(r) of G with vertical bar A(1) boolean OR A(2) boolean OR ... boolean OR A(r)vertical bar <= t, there exist r disjoint cycles C-1, C-2,...,Cr of G such that C-1 boolean OR C-2 boolean OR ... C-r spans G, and C-t contains A(i) for every i. In this paper, we prove that the n-dimensional hypercube Q(n) is spanning 2-cyclable of order n - 1 for n >= 3. Moreover, Q(n) is spanning k-cyclable of order k if k <= n - 1 for n >= 2. The spanning r-cyclability of a graph G is the maximum integer t such that G is spanning r-cyclable of order k for k = r, r + 1,..., t but is not spanning r-cyclable of order t + 1. We also show that the spanning 2-cyclability of Q(n) is n - for n >= 3. (C) 2013 Elsevier B.V. All rights reserved.
Edge-bipancyclicity of conditional faulty hypercubes
(2007-12-31)
Shih, Lun-Min
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
Xu et al. showed that for any set of faulty edges F of an n-dimensional hypercube Q(n) with vertical bar F vertical bar <= n - 1, each edge of Q(n) - F lies on a cycle of every even length from 6 to 2(n), n >= 4, provided not all edges in F are incident with the same vertex. In this paper, we find that under similar condition, the number of faulty edges can be much greater and the same result still holds. More precisely, we show that, for up to vertical bar F vertical bar = 2n - 5 faulty edges, each edge of the faulty hypercube Q(n) - F lies on a cycle of every even length from 6 to 2(n) with each vertex having at least two healthy edges adjacent to it, for n >= 3. Moreover, this result is optimal in the sense that there is a set F of 2n - 4 conditional faulty edges in Q(n) such that Q(n) - F contains no hamiltonian cycle. (c) 2007 Elsevier B.V. All rights reserved.
Embedding Hamiltonian paths in augmented cubes with a required vertex in a fixed position
(2009-11-01)
Lee, Chung-Meng
;
Teng, Yuan-Hsiang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
It is proved that there exists a path P(l)(x, y) of length l if d(AQn) (x, y) <= l <= 2(n) - 1 between any two distinct vertices x and y of AQ(n). Obviously, we expect that such a path P(l)(x, y) can be further extended by including the vertices not in P(l)(x, y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that there exists a hamiltonian path R(x, y, z;l) from x to z such that d(R(x,y,z;l)) (x, y) = l for any three distinct vertices x, y, and z of AQ(n) with n >= 2 and for any d(AQn) (x, y)<= l <= 2(n) - 1 - d(AQn) (y, z). Furthermore, there exists a hamiltonian cycle S(x, y; l) such that d(S(x,y;l)) (x, y) = l for any two distinct vertices x and y and for any d(AQn) (x, y) <= l <= 2(n-1). (C) 2009 Elsevier Ltd. All rights reserved.
Embedding hamiltonian paths in hypercubes with a required vertex in a fixed position
(2008-08-16)
Lee, Chung-Meng
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
;
Department of Computer Science
Assume that n is a positive integer with n >= 2. It is proved that between any two different vertices x and y of Q(n) there exists a path PI(x, y) of length l for any l with h(x, y) <= l <= 2(n) - 1 and 2 vertical bar(l - h(x, y)). We expect such path P-l(x, y) can be further extended by including the vertices not in P-l(x, y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that for any two vertices x and z from different partite set of n-dimensional hypercube Q(n), for any vertex y is an element of V(Q(n)) - {x, z}, and for any integer I with h(x, y) <= l <= 2(n) - l - h(y, z) and 2 vertical bar(l - h(x, y)), there exists a hamiltonian path R(x, y, z; l) from x to z such that d(R(x,y,z,l))(x, y) = l. Moreover, for any two distinct vertices x and y of Q,, and for any integer I with h(x, y) <= l <= 2(n-1) and 2 vertical bar(l - h(x, y)), there exists a hamiltonian cycle S(x, y; l) such that d(S(X,y;l))(x, y) = l. (C) 2008 Elsevier B.V. All rights reserved.
Embedding paths of variable lengths into hypercubes with conditional link-faults
(2009-08-01)
Kueng, Tz-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q(n), in which every node is still incident to at least two fault-free links. Then we show that Q(n) - F has a path of any odd (resp. even) length in the range from the distance to 2(n) - 1 (resp. 2(n) - 2) between two arbitrary nodes even if vertical bar F vertical bar = 2n - 5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults. (C) 2009 Elsevier B.V. All rights reserved.
Fault-free mutually independent Hamiltonian cycles of faulty star graphs
(2011)
Kung, Tzu-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
The star graph interconnection network has been recognized as an attractive alternative to the hypercube for its nice topological properties. Unlike previous research concerning the issue of embedding exactly one Hamiltonian cycle into an injured star network, this paper addresses the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty star network. To be precise, let SG(n) denote an n-dimensional star network in which f <= n - 3 edges may fail accidentally. We show that there exist (n - 2 - f)-mutually independent Hamiltonian cycles rooted at any vertex in SGn if n epsilon {3, 4}, and there exist (n - 1 - f)-mutually independent Hamiltonian cycles rooted at any vertex in SG(n) if n >= 5.
Fault-tolerant hamiltonian connectedness of cycle composition networks
(2008-02-15)
Kueng, Tz-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
It is important for a network to tolerate as many faults as possible. With the graph representation of an interconnection network, a k-regular hamiltonian and hamiltonian connected network is super fault-tolerant hamiltonian if it remains hamiltonian after removing up to k - 2 vertices and/or edges and remains hamiltonian connected after removing up to k - 3 vertices and/or edges. Super fault-tolerant hamiltonian networks have an optimal flavor with regard to the fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity. For this reason, a cycle composition framework was proposed to construct a (k + 2)-regular super fault-tolerant hamiltonian network based on a collection of n k-regular super fault-tolerant hamiltonian networks containing the same number of vertices for it n >= 3 and k >= 5. This paper is aimed to emphasize that the cycle composition framework can be still applied even when k = 4. (c) 2007 Elsevier Inc. All rights reserved.
Fault-tolerant hamiltonian connectivity of the WK-recursive networks
(2014-07-01)
Ho, Tung-Yang
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
Many research on the WK-recursive network has been published during the past several years due to its favorite properties. In this paper, we consider the fault-tolerant hamiltonian connectivity of the WK-recursive network. We use K(d, t) to denote the WK-recursive network of level t, each of which basic modules is a d-vertex complete graph, where d > 1 and t >= 1. The fault-tolerant hamiltonian connectivity H-f(k)(G) is defined to be the maximum integer k such that G is k fault-tolerant hamiltonian connected if G is hamiltonian connected and is undefined otherwise. In this paper, we prove that H-f(k)(K(d, t)) = d - 4 if d >= 4. (C) 2014 Elsevier Inc. All rights reserved.