標題: 增強立方體之容錯漢米爾頓性質
Fault Hamiltonicity of Augmented Cubes
作者: 江良志
Liang-Chih Chiang
徐力行
譚建民
Dr. Lih-Hsing Hsu
Dr. Jimmy J. M. Tan
資訊科學與工程研究所
關鍵字: 容錯;漢米爾頓;漢米爾頓連結;增強立方體;fault-tolerant;hamiltonian;hamiltonian connected;augmented cubes
公開日期: 2002
摘要: 增強立方體是由根據某規則來增加一些連線到立方體上而衍生出來的。在這篇論文裡,我們討論增強立方體的容錯漢米爾頓性質與容錯漢米爾頓連結性質,假設錯誤集合為n維增強立方體的點集合與邊集合的聯集之子集合,以及n大於等於4,若錯誤集合的勢小於等於2n-3,我們可證明n維增強立方體減去錯誤集合是漢米爾頓,若錯誤集合的勢小於等於2n-4,我們可證明n維增強立方體是漢米爾頓連結,此外,這些上限是最佳的。
Augmented cube, is derived by adding some more edges to hypercube according to some rule. In this paper, we consider the fault hamiltonicity and the fault hamiltonian connectivity of the n-dimensional augmented cubes. Assume that the fault set is a subset of the union of vertex set and edge set of the n-dimensional augmented cube and n is equal to or larger than 4. We prove that the n-dimensional augmented cube subtracting the fault set is hamiltonian if the cardinality of the fault set is equal to or less than 2n-3 and the n-dimensional augmented cube subtracting the fault set is hamiltonian connected if the fault set is equal to or less than 2n-4. Furthermore, these bounds are tight.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT910394007
http://hdl.handle.net/11536/70180
Appears in Collections:Thesis