Cycle embedding in faulty wrapped butterfly graphs
檔案
- 000184921100002.pdf (251.9 KB, Adobe PDF)
日期
2003-09-01
作者
類型
系所
期刊名稱
NETWORKS
卷期與頁次
第 42 卷第 2 期,頁 85–96
ISSN
0028-3045
語言
英文
摘要
In this paper, we study the maximal length of cycle embedding in a faulty wrapped butterfly graph BFn with at most two faults in vertices and/or edges. When there is one vertex fault and one edge fault, we prove that the maximum cycle length is n2(n) - 2 if n is even and n2(n) - 1 if n is odd. When there are two faulty vertices, the maximum cycle length is n2(n) - 2 for odd n. All these results are optimal because the wrapped butterfly graph is bipartite if and only if n is even. (C) 2003 Wiley Periodicals, Inc.