Browsing by Author "Ho, Tung-Yang"

Now showing 1 - 10 of 10

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 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.
Fault-Tolerant Hamiltonian Connectivity and Fault-Tolerant Hamiltonicity of the Fully Connected Cubic Networks
(2009-11-01)
Ho, Tung-Yang
;
Lin, Cheng-Kuan
;
資訊工程學系
;
Department of Computer Science
Many papers on the fully connected cubic networks have been published for the past several years due to its favorite properties. In this paper, we consider the fault-tolerant hamiltonian connectivity and fault-tolerant hamiltonicity of the fully connected cubic network. We use FCCN(n) to denote the fully connected cubic network of level n. Let G = (V, E) be a graph. The fault-tolerant hamiltonian connectivity H(f)(k) (G) is defined to be the maximum integer l such that G - F remains hamiltonian connected for every F subset of V(G) boolean OR E(G) with vertical bar F vertical bar <= l. The fault-tolerant hamiltonicitly H(f)(G) is defined to be the maximum integer l such that G - F remains hamiltonian for every F subset of V(G) boolean OR E(G) with vertical bar F vertical bar <= l. We prove that H(f)(k) (FCCN(n)) = 0 and H(f)(FCCN(n)) = 1 if n >= 2.
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.
Fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity of the folded Petersen cube networks
(2009)
Lin, Cheng-Kuan
;
Ho, Tung-Yang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
Some research on the folded Petersen cube networks have been published for the past several years due to its favourite properties. In this paper, we consider the fault-tolerant hamiltonicity and the fault-tolerant hamiltonian connectivity of the folded Petersen cube networks. We use FPQn, k to denote the folded Petersen cube networks of parameters n and k. In this paper, we show that FPQn, k-F remains hamiltonian for any F V(FPQn, k)E(FPQn, k) with |F|n+3k-2 and FPQn, k-F remains hamiltonian connected for any F V(FPQn, k)E(FPQn, k) with |F|n+3k-3 if (n, k){(0, 1)}{(n, 0) | n is a positive integer}. Moreover, this result is optimal.
Fault-Tolerant Hamiltonicity of the WK-Recursive Networks
(2009)
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. The fault-tolerant hamiltonian connectivity 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 the fault-tolerant hamiltonian connectivity of K(d,t) is d-4.
Mutually orthogonal hamiltonian connected graphs
(2009-09-01)
Ho, Tung-Yang
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
in this work, we concentrate on those n-vertex graphs G with n >= 4 and (e) over bar <= n - 4. Let P(1) = < u(1), u(2),..., u(n)) and P(2) = (v(1), v(2),..., v(n)) be any two hamiltonian paths of G. We say that P(1) and P(2) are orthogonal if u(1) = v(1), u(n) = v(n), and u(q) not equal v(q) for q is an element of {2, n - 1}. We say that a set of hamiltonian paths {P(1), P(2),..., P(s)} of G are mutually orthogonal if any two distinct paths in the set are orthogonal. We will prove that there are at least two orthogonal hamiltonian paths of G between any two different vertices. Furthermore, we classify the cases such that there are exactly two orthogonal hamiltonian paths of G between any two different vertices. Aside from these special cases, there are at least three mutually orthogonal hamiltonian paths of G between any two different vertices. (C) 2009 Elsevier Ltd. All rights reserved.
On the extremal number of edges in hamiltonian connected graphs
(2010-01-01)
Ho, Tung-Yang
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, D. Frank
;
Hsu, Lih-Hsing
Assume that n and delta are positive integers with 3 <= delta < n. Let hc(n, delta) be the minimum number of edges required to guarantee an n-vertex graph G with minimum degree delta(G) >= delta to be haimiltonian connected. Any n-vertex graph G with delta(G) >= delta is hamiltonian connected if vertical bar E(G)vertical bar >= hc(n, delta). We prove that hc(n, delta) = C(n - delta + 1, 2) + delta(2) - delta + 1 if delta <= [n+3x(n mod 2)/6] + 1, hc(n, delta) = C(n - [n/2] + 1, 2) + [n/w](2) - [n/2] + 1 if [n+3x(n mod 2)/6] + 1 < delta <= [n/2], and hc(n, delta) = [n delta/2] if delta > [n/2]. (C) 2009 Elsevier Ltd. All rights reserved.
On the Extremal Number of Edges in Hamiltonian Graphs
(2011-09-01)
Ho, Tung-Yang
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Hsu, D. Frank
;
Hsu, Lih-Hsing
Assume that n and delta are positive integers with 2 <= delta < n. Let h(n, delta) be the minimum number of edges required to guarantee an n-vertex graph with minimum degree delta(G) >= delta be hamiltonian, i.e., any n-vertex graph G with delta(G) >= delta is hamiltonian if vertical bar E(G)vertical bar >= h(n, delta). We move that h(n, delta) = (n - delta, 2) + delta(2) +1 if delta <= left perpendicular n + 1 + x ((n + 1mld 2)/6 right perpendicular, h(n, delta) = C(n - left perpendicular n - 1/2 right perpendicular, 2) + left perpendicular n - 1/2 right perpendicular(2) + 1 if left perpendicular n + 1 + 3 x ((n + 1) mod2)/6 < delta <= left perpendicular n - 1/2 right perpendicular, and h(n, delta, = inverted right perpendicular n delta/2inverted left perpendicular if delta > left perpendicular n - 1/2 right perpendicular.
Super Spanning Connectivity of Augmented Cubes
(2012-04-01)
Lin, Cheng-Kuan
;
Ho, Tung-Yang
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
A k-container C(u, v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u, v) of G is a k*-container if it contains all nodes of G. A graph G is k*-connected if there exists a k*-container between any two distinct nodes. The spanning connectivity of G, kappa* (G), is defined to be the largest integer k such that G is omega*-connected for all 1 <= omega <= k if G is an 1*-connected graph and undefined if otherwise. A graph G is super spanning connected if kappa*(G) = kappa(G). In this paper, we prove that the n-dimensional augmented cube AQ(n) is super spanning connected.