Hamiltonian-connectivity and strongly Hamiltonian-laceability of folded hypercubes

被引：55

作者：

Hsieh, Sun-Yuan ^{[1
]}

Kuo, Che-Nan ^{[1
]}

机构：

[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 70101, Taiwan

来源：

COMPUTERS & MATHEMATICS WITH APPLICATIONS | 2007年 / 53卷 / 07期

关键词：

hypercubes; folded hypercubes; Hamiltonian-connectivity; strongly Hamiltonian-laceability; bipartite graphs;

D O I：

10.1016/j.camwa.2006.10.033

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we analyze a hypercube-like structure, called the folded hypercube, which is basically a standard hypercube with some extra links established between its nodes. We first show that the n-dimensional folded hypercube is bipartite when n is odd. We also show that the n-dimensional folded hypercube is strongly Hamiltonian-laceable when n is odd, and is Hamiltonian-connected when n = 1 or n (>= 2) is even. (C) 2007 Elsevier Ltd. All rights reserved.

引用

页码：1040 / 1044

页数：5

共 18 条

[1]

Akl S.G., 1997, Parallel Computation: Models and Methods

[2]

ASCHEUER N, 1995, THESIS U TECHNOLOGY

[3]

Bermond J.C., 1992, DISCRETE APPL MATH, P37

[4]

BHUYAN LN, 1984, IEEE T COMPUT, V33, P323, DOI 10.1109/TC.1984.1676437

[5] PROPERTIES AND PERFORMANCE OF FOLDED HYPERCUBES [J].

ELAMAWY, A ;

LATIFI, S .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1991, 2 (01) :31-42

[6] THE TWISTED N-CUBE WITH APPLICATION TO MULTIPROCESSING [J].

ESFAHANIAN, AH ;

NI, LM ;

SAGAN, BE .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (01) :88-93

[7]

Hsieh SY, 2000, NETWORKS, V36, P225, DOI 10.1002/1097-0037(200012)36:4<225::AID-NET3>3.0.CO

[8]

2-G

[9]

HSU DF, 1993, NETWORKS, V23

[10]

JWO JS, 1991, J CIRCUIT SYST COMP, V1, P43, DOI DOI 10.1142/S0218126691000215

← 1 2 →