在一些聯結網路圖形上的互相獨立之漢米爾頓迴圈

互相獨立的漢米爾頓迴圈已經在連結網路上有著廣泛研究。在本篇論文中，我們針對一些特定的圖形上的互相獨立漢米爾頓迴圈性質做研究，包括：當 $k$ 為偶數之 $k$ 位元 $n$ 維度立方體$(Q_{n}^{k})$、迴圈合成網路$(CCN_k)$、交錯群圖$(AG_n)$以及排列圖$(A_{n,k})$上互相獨立的漢米爾頓迴圈的建構。我們所得的結果為最佳的，意即我們所建構的獨立漢米爾頓迴圈數是最多的。除了上述特定圖形中互相獨立的漢米爾頓迴圈的建構方法之外，我們也希望能對一般的圖形上互相獨立的漢米爾頓迴圈的存在性找到它們的充分必要條件。根據已知的結果，我們也得到了一個猜想。

關鍵字

單點容錯漢米爾頓性. ；排列圖；交錯群圖；迴圈合成網路； $k$ 位元 $n$ 維度立方體；互相獨立；漢米爾頓迴圈

並列摘要

Abstract Mutually independent hamiltonian cycles, abbreviated as MIHCs, have been studied on interconnection networks widely. In this dissertation, we study MIHCs on some specific graphs. We established the existence of MIHCs in $k$-ary $n$-cubes $(Q_{n}^{k})$ when $k$ is even, cycle composition networks $(CCN_k)$, alternating group graphs $(AG_n)$ and arrangement graphs $(A_{n,k})$. The results are shown to be optimal in the sense that the number of MIHCs we constructed is maximal. In addition to the construction schemes of MIHCs for specific graphs, we intend to give some sufficient and necessary conditions for the existence of MIHCs in general graphs. A conjecture is given based on known results.

並列關鍵字

1-fault-tolerant hamiltonian. ； arrangement graphs ； alternating group graphs ； cycle composition networks ； $k$-ary $n$-cubes ； hamiltonian cycle ； mutually independent

參考文獻

[1] S.B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks. IEEE Transactions on Computers, 34 (1989), no.4, 555–566.

[3] B. Alspach and D. Hare, Edge-pancyclic block-intersection graphs. Discrete Mathematics, 97 (1997), 17–24.

[4] H.R. Arabnia, A parallel algorithm for the arbitrary rotation of digitized images using process-and-data-decomposition approach. Journal of Parallel and Distributed Computing, 10(2) (1990), 188–192.

[5] Y.A. Ashir and I.A. Stewart, On embedding cycles in k-ary n-cubes. Parallel Processing Letters, 7(1997), 49–55.

[6] S. Bettayeb, On the k-ary hypercube. Theoretical Computer Science, 140(1995), 333–339.

國際替代計量

在一些聯結網路圖形上的互相獨立之漢米爾頓迴圈

全文下載

主題瀏覽