✦ LIBER ✦

Construction schemes for fault-tolerant Hamiltonian graphs

✍ Scribed by Wang, Jeng-Jung; Hung, Chun-Nan; Tan, Jimmy J. M.; Hsu, Lih-Hsing; Sung, Ting-Yi

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 319 KB
Volume: 35
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(200005)35:3<233::aid-net7>3.0.co;2-f

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we present three construction schemes for fault-tolerant Hamiltonian graphs. We show that applying these construction schemes on fault-tolerant Hamiltonian graphs generates graphs preserving the original Hamiltonicity property. We apply these construction schemes to generate some known families of optimal 1-Hamiltonian graphs in the literature and the Hamiltonicity properties of these graphs are the direct consequence of the construction schemes. In addition, we can use these construction schemes to propose new family of optimal 1-Hamiltonian graphs.

📜 SIMILAR VOLUMES

Fault-tolerant graphs for tori

✍ Yamada, Toshinori; Ueno, Shuichi 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 2 views

Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph G from H by adding a minimum number D(t, H) of edges such that even after deleting any t edges from G the remaini