Browsing by Author "Huang, Hua-Min"

Now showing 1 - 7 of 7

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.
Mutually independent hamiltonian cycles for the pancake graphs and the star graphs
(2009-09-06)
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Huang, Hua-Min
;
Hsu, D. Frank
;
Hsu, Lih-Hsing
A hamiltonian cycle C of a graph G is an ordered set < u(1), u(2,) ..., u(n(G)), u(1)> of vertices such that u(i) not equal u(j) for i not equal j and u(i) is adjacent to u(i+1) for every i is an element of {1, 2, ..., n(G) - 1} and u(n(G)) is adjacent to u(1), where n(G) is the order of G. The vertex u(1) is the starting vertex and u(i) is the ith vertex of C. Two hamiltonian cycles 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) and u(i) not equal v(i) for every i is an element of {2, 3, ..., n(G)}. A set of hamiltonian cycles {C(1), C(2), ..., C(k)} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph 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, the mutually independent hamiltonicity is considered for two families of Cayley graphs, the n-dimensional pancake graphs P(n) and the n-dimensional star graphs S(n). It is proven that IHC(P(3)) = 1, IHC(P(n)) = n - 1 if n >= 4, IHC(S(n)) = n - 2 if n is an element of {3, 4} and IHC(S(n)) = n - 1 if n >= 5. (C) 2009 Elsevier B.V. All rights reserved.
On spanning connected graphs
(2008-04-06)
Lin, Cheng-Kuan
;
Huang, Hua-Min
;
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 the set of the vertices of all the paths in C(u, v) contains all the vertices of G. A graph G is k*-connected if there exists a k*-container between any two distinct vertices. Therefore, a graph is 1*-connected (respectively, 2*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k*-connected graphs. (c) 2007 Published by Elsevier B.V.
On the spanning w-wide diameter of the star graph
(2006-12-01)
Lin, Cheng-Kuan
;
Huang, Hua-Min
;
Hsu, D. Frank
;
Hsu, Lih-Hsing
;
資訊工程學系
Let a and v be any two distinct nodes of an undirected graph G, which is k-connected. A container C(u, v) between a and v is a set of internally disjoint paths {P(1), P(2),..., P(W)} between a and v where 1 <= w <= k. The width of C(u, v) is w and the length of C(u, v) {written as I[C(u, v)]} is max{I(P(i)) 1 <= I <= w}. A w-container C(u, v) is a container with width w. The w-wide distance between u and v, d(w)(u, v), is min{I(C(u, v)) C(u, v) is a w-container). A w-container C(u, v) of the graph G is a w*-container if every node of G is incident with a path in C(u, v). That means that the w-container C(u, v) spans the whole graph. Let S(n) be the n-dimensional star graph with n >= 5. It is known that S(n) is bipartite. In this article, we show that, for any pair of distinct nodes u and v in different partite sets of S(n), there exists an (n - 1)*-container C(u, v) and the (n - 1)-wide distance d((n-1))(u, v) is less than or equal to n!/n-2 + 1. In addition, we also show the existence of a 2*-container C(u, v) and the 2-wide distance d(2)(u, v) is bounded above by nI/2 + 1. (C) 2006 Wiley Periodicals, Inc.
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."
The super spanning connectivity and super spanning laceability of the enhanced hypercubes
(2009-04-01)
Chang, Chung-Hao
;
Lin, Cheng-Kuan
;
Tan, Jimmy J. M.
;
Huang, Hua-Min
;
Hsu, Lih-Hsing
A k -container C(u,v) of a graph G is a set of k disjoint paths between u and v. A k-container C(u,v) of G is a k (*) -container if it contains all vertices of G. A graph G is k (*) -connected if there exists a k (*)-container between any two distinct vertices of G. Therefore, a graph is 1(*)-connected (respectively, 2(*)-connected) if and only if it is Hamiltonian connected (respectively, Hamiltonian). A graph G is super spanning connected if there exists a k (*)-container between any two distinct vertices of G for every k with 1a parts per thousand currency signka parts per thousand currency sign kappa(G) where kappa(G) is the connectivity of G. A bipartite graph G is k (*) -laceable if there exists a k (*)-container between any two vertices from different partite set of G. A bipartite graph G is super spanning laceable if there exists a k (*)-container between any two vertices from different partite set of G for every k with 1a parts per thousand currency signka parts per thousand currency sign kappa(G). In this paper, we prove that the enhanced hypercube Q (n,m) is super spanning laceable if m is an odd integer and super spanning connected if otherwise.