增強立方體之容錯漢米爾頓性質

Abstract

增強立方體是由根據某規則來增加一些連線到立方體上而衍生出來的。在這篇論文裡，我們討論增強立方體的容錯漢米爾頓性質與容錯漢米爾頓連結性質，假設錯誤集合為ｎ維增強立方體的點集合與邊集合的聯集之子集合，以及ｎ大於等於４，若錯誤集合的勢小於等於２ｎ－３，我們可證明ｎ維增強立方體減去錯誤集合是漢米爾頓，若錯誤集合的勢小於等於２ｎ－４，我們可證明ｎ維增強立方體是漢米爾頓連結，此外，這些上限是最佳的。

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.