(n, k)-星形圖壞邊容錯之弱泛迴圈性質

(n-3)-Edge-Fault-Tolerant Weak-Pancyclicity of (n, k)-Star Graphs

陳子龍(Tzu-Lung Chen)

指導教授 ： 杜迪榕

共同指導教授 ： 王有禮(Yue-Li Wang)

國立暨南國際大學/科技學院/資訊工程學系/碩士(2009年)

https://doi.org/10.6837/NCNU.2009.00148

摘要

(n, k)-星形圖是個廣義版本的的n-星形圖，並且符合Cayley圖的定義。(n, k)-星形圖在建立大型平行計算系統時，是一個超立方體的極佳替代圖。在最近的研究，已經有人提出在一個(n, k)-星形圖中，它的弱節點泛迴圈性質，也就是說，在一個(n, k)-星形圖中，長度範圍從6到n!/(n-k)!的迴圈都可以包含任何指定的一個點。在本研究中，更進一步提出在一個(n, k)-星形圖中，如果壞掉的邊不超過n-3個的情況下，它仍然保有長度範圍從6到n!/(n-k)!的迴圈，對於所有n >= 4 而且 1 <= k < n。由於在(n, k)-星形圖中任何一個點，它所連結的邊都是n-1個，所以關於壞邊容錯的數目，本研究結果已是最佳化。

關鍵字

弱泛迴圈 ； (n, k)-星形圖 ； Cayley圖 ； 內嵌迴圈 ； 容錯

並列摘要

The (n, k)-star graph is a generalized version of the n-star graph, which belongs to the class of Cayley graphs, and has been recognized as an attractive alternative to an n-cube for building massively parallel computers. Recently, Chen et al. showed that an (n, k)-star graph is 6-weak-vertex-pancyclic for k < n-1, that is, each vertex of an (n, k)-star graph is contained in a cycle of length ranged from 6 to n!/(n-k)!. This work demonstrates that an (n, k)-star graph remains 6-weak-pancyclic, even if there are up to n-3 edge faults, where n >= 4 and 1 <= k < n. Since an (n, k)-star graph is regular of degree n-1, the result of this work is optimal with respect to the number of edge faults tolerated.

並列關鍵字

Weak-pancyclicity ； (n, k)-star graph ； Cayley graph ； cycle embedding ； fault-tolerance

參考文獻

[1] S.B. Akers, D. Harel, and B. Krishnamurthy, “The star graph: an attractive alternative to the n-cube,” in Proceedings of the International Conference on Parallel Processing, 1987, pp. 393–400.

[2] J.A. Bondy, “Pancyclic graphs,” Journal of Combinatorial Theory Series B, vol. 11, pp. 80–84, 1971.

[3] N.W. Chang, “Hamiltonian path embedding and pancyclicity on the Möbius cube with faulty nodes and faulty edges,” IEEE Transactions on Computers, vol. 55, no. 7, pp. 854–863, Jul. 2006.

[4] J.H. Chang and J. Kim, “Ring embedding in faulty (n, k)-star graphs,” in Proceedings of the 8th International Conference on Parallel and Distributed Systems (ICPADS’01), 2001, pp. 99–106.

[5] Y.S. Chen and K.S. Tai, “A near-optimal broadcasting in (n, k)-star graphs,” in Proceedings of the ACIS International Conference on Software Engineering Applied to Networking and Parallel/Distributed Computing (SNPD’00), 2000, pp. 217–224.