Optimal Fault-Tolerant Hamiltonian and Hamiltonian Connected Graphs

Y-Chuang Chen; Yong-Zen Huang; Lih Hsing Hsu; Jiann-Mean Tan

Optimal Fault-Tolerant Hamiltonian and Hamiltonian Connected Graphs

Y-Chuang Chen, Yong-Zen Huang, Lih Hsing Hsu, Jiann-Mean Tan

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	International Electronic Conference on Computer Science
Pages	344-346
Number of pages	3
Volume	1060
State	Published - 2008

Keywords

Twisted-cubes; Crossed-cubes; Mobius cubes; generalized hypercubes; recursive circulant graphs; optimal fault-tolerant
GENERALIZED HYPERCUBE; NETWORKS; CUBES

Fingerprint Dive into the research topics of 'Optimal Fault-Tolerant Hamiltonian and Hamiltonian Connected Graphs'. Together they form a unique fingerprint.

Cite this

@inproceedings{d77731dcd2f14876ae1b2204b2a0255c,

title = "Optimal Fault-Tolerant Hamiltonian and Hamiltonian Connected Graphs",

abstract = "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.",

keywords = "Twisted-cubes; Crossed-cubes; Mobius cubes; generalized hypercubes; recursive circulant graphs; optimal fault-tolerant, GENERALIZED HYPERCUBE; NETWORKS; CUBES",

author = "Y-Chuang Chen and Yong-Zen Huang and Hsu, {Lih Hsing} and Jiann-Mean Tan",

year = "2008",

language = "English",

volume = "1060",

pages = "344--346",

booktitle = "International Electronic Conference on Computer Science",

}

TY - GEN

T1 - Optimal Fault-Tolerant Hamiltonian and Hamiltonian Connected Graphs

AU - Chen, Y-Chuang

AU - Huang, Yong-Zen

AU - Hsu, Lih Hsing

AU - Tan, Jiann-Mean

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

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

KW - GENERALIZED HYPERCUBE; NETWORKS; CUBES

M3 - Conference contribution

VL - 1060

SP - 344

EP - 346

BT - International Electronic Conference on Computer Science

ER -