標題: 遞迴式循環圖泛圈容錯性質研究
Fault-Tolerant Pancyclicity of Recursive Circulant Graphs
作者: 鄭斐文
Fei-Wen Cheng
徐力行
Lih-Hsing Hsu
資訊科學與工程研究所
關鍵字: 容錯;弱泛圈性質;遞迴式循環圖;fault-tolerant;weakly pancyclic;recursive circulant graph
公開日期: 2002
摘要: 在這篇論文當中,我們討論遞迴式循環圖,$G(N,d)$,的泛圈容錯性質。$G(N,d)$,是由Park及Chwa在1994年提出。他們同時也證明出$G(cd^k,d)$是正則圖。我們假設$F$為在$G(cd^k,d)$裡的任意錯誤集合,其中$F\subset E(G(cd^k,d))\cup V(G(cd^k,d))$。在這篇論文中,我們證明$G(cd^k,d)-F$其中$|F|\leq deg(G(cd^k,d))-2$是弱泛圈性質當c是奇數而且$c\geq 3$。換句話說,此上限是最佳的。
In this thesis, we consider the weakly pancyclic property on the
faulty recursive circulant graph, $G(N,d)$. $G(N,d)$ was proposed in 1994 by Park and Chwa \cite{Park}. They also proved that $G(cd^k,d)$ is regular graph. Let $F$ be any faulty set in
$G(cd^k,d)$ such that $F\subset E(G(cd^k,d))\cup V(G(cd^k,d))$. In this thesis, we proved that $G(cd^k,d)-F$ with $|F|\leq
deg(G(cd^k,d))-2$ is weakly pancyclic where $c$ is odd, and $c\geq 3$. Moreover, this bound is tight.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT910394010
http://hdl.handle.net/11536/70183
顯示於類別:畢業論文