Title: Embedding cycles in IEH graphs
Authors: Chang, HY
Chen, RJ
資訊工程學系
Department of Computer Science
Keywords: hypercubes;embedding;Hamiltonian cycles;Incrementally Extensible Hypercubes;interconnection networks
Issue Date: 14-Oct-1997
Abstract: We embed cycles into IEH graphs. First, IEH graphs are proved to be Hamiltonian except when they are of size 2(n) -1 for all n greater than or equal to 2. Next, we show that for an IEH graph of size N, an arbitrary cycle of even length N-e where 3 < N-e < N is found. We also find an arbitrary cycle of odd length N-o where 2 < N-o < N if and only if a node of this graph has at least one forward 2-Inter-Cube (IC) edges. These results help describe the whole cycle structure in IEH graphs. (C) 1997 Elsevier Science B.V.
URI: http://hdl.handle.net/11536/255
ISSN: 0020-0190
Journal: INFORMATION PROCESSING LETTERS
Volume: 64
Issue: 1
Begin Page: 23
End Page: 27
Appears in Collections:Articles


Files in This Item:

  1. A1997YG01100004.pdf