(n,k)星狀圖之容錯漢米爾頓性質與容錯漢米爾頓連通性質

Abstract

在這篇論文中，我們考慮(n,k)星狀圖Sn,k的容錯漢米爾頓性質與容錯漢米爾頓連通性質。假設F □ V(Sn,k) □ E(Sn,k)，在n – k □ 2的情況下。我們可以證明當|F | ≤ n – 3時，Sn,k – F會有漢米爾頓環路，並且當|F | ≤ n – 4時，Sn,k –F會有漢米爾頓連結。當n – k = 1時，Sn,n-1的圖形與星狀圖Sn為同構，且我們知道當n > 2時，Sn有漢米爾頓環路，並且只有當n = 2時，Sn才有漢米爾頓連結。

In this paper, we consider the fault hamiltonicity and fault hamiltonian connectivity of the (n, k)-star graph Sn,k. Assume that F □ V(Sn,k) □ E(Sn,k). For n – k □ 2, we prove that Sn,k – F is hamiltonian if |F | ≤ n – 3 and Sn,k – F is hamiltonian connected if |F | < n – 4. For n – k = 1, Sn,n-1 is isomorphic to the star graph Sn and it is Known that Sn is hamiltonian if and only if n > 2 and Sn is hamiltonian connected if and only if n = 2. Moreover, all the bounds are tight.