Browsing by Author "Kao, SS"

Now showing 1 - 3 of 3

Brother trees: A family of optimal 1(p)-hamiltonian and 1-edge hamiltonian graphs
(2003-06-15)
Kao, SS
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
In this paper we propose a family of cubic bipartite planar graphs, brother trees, denoted by BT(n) with n greater than or equal to 2. Any BT(n) is hamiltonian. It remains hamiltonian if any edge is deleted. Moreover, it remains hamiltonian when a pair of nodes (one from each partite set) is deleted. These properties are optimal. Furthermore, the number of nodes in BT(n) is 6. 2(n) - 4 and the diameter is 2n + 1. (C) 2003 Elsevier Science B.V. All rights reserved.
Spider web networks: a family of optimal, fault tolerant, hamiltoman bipartite graphs
(2005-01-05)
Kao, SS
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a honeycomb mesh variation, called a spider web network. Assume that in and it are positive even integers with m greater than or equal to 4. A spider web network SW(m, n) is a 3-regular bipartite planar graph with bipartition C and D. We prove that the honeycomb rectangular mesh HREM(m, n) is a spanning subgraph of SW(m, n). We also prove that SW(m, n) - e is harniltonian for any e is an element of E and SW(m, n) - {c, d} remains hamiltonian for any c is an element of C and d is an element of D. These hamiltonian propel-ties are optimal. (C) 2003 Elsevier Inc. All rights reserved.
Super-connectivity and super-edge-connectivity for some interconnection networks
(2003-08-10)
Chen, YC
;
Tan, JJM
;
Hsu, LH
;
Kao, SS
;
資訊工程學系
Let G = (V, E) be a k-regular graph with connectivity K and edge connectivity. G is maximum connected if kappa = k, and G is maximum edge connected if lambda = k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x(v,x) is an element of E} for some vertex v is an element of V; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)(v,x) is an element of E} for some vertex v is an element of V. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, mobius cubes, split-stars, and recursive circulant graphs. (C) 2002 Elsevier Science Inc. All rights reserved.