Ring embedding in faulty pancake graphs |
| |
Authors: | Chun-Nan Hung Hong-Chun Hsu Lih-Hsing Hsu |
| |
Affiliation: | a Department of Computer Science and Information Engineering, Da-Yet University, Changhua 51505, Taiwan, R.O.C. b Department of Computer and Information Science, National Chiao Tung University, Hsinchu 300, Taiwan, R.O.C. |
| |
Abstract: | In this paper, we consider the fault hamiltonicity and the fault hamiltonian connectivity of the pancake graph Pn. Assume that F⊆V(Pn)∪E(Pn). For n?4, we prove that Pn−F is hamiltonian if |F|?(n−3) and Pn−F is hamiltonian connected if |F|?(n−4). Moreover, all the bounds are optimal. |
| |
Keywords: | Fault tolerance Hamiltonian Hamiltonian connected Pancake graphs |
本文献已被 ScienceDirect 等数据库收录! |
|