Optimal Fault-Tolerant Hamiltonian and Hamiltonian Connected Graphs

被引：0

作者：

Chen, Y-Chuang ^{[1
]}

Huang, Yong-Zen ^{[2
]}

Hsu, Lih-Hsing ^{[3
]}

Tan, Jimmy J. M. ^{[2
]}

机构：

[1] Ming Hsin Univ Sci & Technol, Dept Informat Management, Hsinchu 304, Taiwan

[2] Natl Chiao Tung Univ, Dept Comp Sci, Hsinchu 300, Taiwan

[3] Providence Univ, Dept Comp Sci & Informat Engn, Taichung 433, Taiwan

来源：

INTERNATIONAL ELECTRONIC CONFERENCE ON COMPUTER SCIENCE | 2008年 / 1060卷

关键词：

Twisted-cubes; Crossed-cubes; Mobius cubes; generalized hypercubes; recursive circulant graphs; optimal fault-tolerant;

D O I：

暂无

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

A k-regular hamiltonian and hamiltonian connected graph G is optimal fault-tolerant hamiltonian and hamiltonian connected if G remains hamiltonian after removing at most k - 2 nodes and/or edges and remains hamiltonian connected after removing at most k - 3 nodes and/or edges. In this paper, we investigate a construction scheme to construct optimal fault-tolerant hamiltonian and hamiltonian connected graphs. Hence, some of the generalized hypercubes, Twisted-cubes, Crossed-cubes, and Mobius cubes are optimal fault-tolerant hamiltonian and optimal fault-tolerant hamiltonian connected.

引用

页码：345 / +

页数：2

共 50 条

[1] Construction schemes for fault-tolerant Hamiltonian graphs
Wang, JJ
Hung, CN
Tan, JJM
Hsu, LH
Sung, TY
NETWORKS, 2000, 35 (03) : 233 - 245
[2] On some super fault-tolerant Hamiltonian graphs
Chen, YC
Tsai, CH
Hsu, LH
Tan, JJM
APPLIED MATHEMATICS AND COMPUTATION, 2004, 148 (03) : 729 - 741
[3] Fault-Tolerant Hamiltonian Connectivity and Fault-Tolerant Hamiltonicity of the Fully Connected Cubic Networks
Ho, Tung-Yang
Lin, Cheng-Kuan
JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 2009, 25 (06) : 1855 - 1862
[4] OPTIMAL FAULT-TOLERANT ROUTINGS FOR CONNECTED GRAPHS
WADA, K
LUO, Y
KAWAGUCHI, K
INFORMATION PROCESSING LETTERS, 1992, 41 (03) : 169 - 174
[5] A recursively construction scheme for super fault-tolerant hamiltonian graphs
Chen, Y-Chuang
Hsu, Lih-Hsing
Tan, Jimmy J. M.
APPLIED MATHEMATICS AND COMPUTATION, 2006, 177 (02) : 465 - 481
[6] HAMILTONIAN GRAPHS WITH MINIMUM NUMBER OF EDGES FOR FAULT-TOLERANT TOPOLOGIES
MUKHOPADHYAYA, K
SINHA, BP
INFORMATION PROCESSING LETTERS, 1992, 44 (02) : 95 - 99
[7] A family of Hamiltonian and Hamiltonian connected graphs with fault tolerance
Y-Chuang Chen
Yong-Zen Huang
Lih-Hsing Hsu
Jimmy J. M. Tan
The Journal of Supercomputing, 2010, 54 : 229 - 238
[8] A family of Hamiltonian and Hamiltonian connected graphs with fault tolerance
Chen, Y-Chuang
Huang, Yong-Zen
Hsu, Lih-Hsing
Tan, Jimmy J. M.
JOURNAL OF SUPERCOMPUTING, 2010, 54 (02): : 229 - 238
[9] FAULT-TOLERANT HAMILTONIAN LACEABILITY AND FAULT-TOLERANT CONDITIONAL HAMILTONIAN FOR BIPARTITE HYPERCUBE-LIKE NETWORKS
Lin, Cheng-Kuan
Ho, Tung-Yang
Tan, Jimmy J. M.
Hsu, Lih-Hsing
JOURNAL OF INTERCONNECTION NETWORKS, 2009, 10 (03) : 243 - 251
[10] Fault-tolerant hamiltonian laceability of hypercubes
Tsai, CH
Tan, JJM
Liang, TN
Hsu, LH
INFORMATION PROCESSING LETTERS, 2002, 83 (06) : 301 - 306

← 1 2 3 4 5 →