Browsing by Author "Teng, YH"

Now showing 1 - 2 of 2

Honeycomb rectangular disks
(2005-03-01)
Teng, YH
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a variation of honeycomb meshes. A honeycomb rectangular disk HReD(m,n) is obtained from the honeycomb rectangular mesh HReM(m,n) by adding a boundary cycle. A honeycomb rectangular disk HReD(m,n) is a 3-regular planar graph. It is obvious that the honeycomb rectangular mesh HReM(m,n) is a subgraph of HReD(m,n). We also prove that HReD(m,n) is hamiltonian. Moreover, HReD(m,n) -f remains hamiltonian for any f is an element of V(HReD(m, n)) boolean OR E(HReD(m, n)) if n >= 6. (c) 2005 Elsevier B.V. All rights reserved.
On mutually independent hamiltonian paths
(2006-04-01)
Teng, YH
;
Tan, JJM
;
Ho, TY
;
Hsu, LH
;
資訊工程學系
Let P-1=< v(1), v(2), v(3),...,v(n)> and P-2=< u(1), u(2), u(3),...,u(n)> be two hamiltonian paths of G. We say that P-1 and P-2 are independent if u(1)=v(1), u(n)=v(n), and u(i)not equal v(i) for 1= 4. We prove that there are at least n-2-(e) over bar mutually independent hamiltonian paths between any pair of distinct vertices of G except n=5 and (e) over bar =1. Assume that G is a graph with the degree sum of any two non-adjacent vertices being at least n+2. Let u and v be any two distinct vertices of G. We prove that there are deg(G)(u)+deg(G)(v)-n mutually independent hamiltonian paths between u and v if (u, v) is an element of E (G) and there are deg(G)(u)+deg(G)(v)-n+2 mutually independent hamiltonian paths between u and v if otherwise. (C) 2005 Elsevier Ltd. All rights reserved.