遞迴式循環圖泛圈容錯性質研究

Abstract

在這篇論文當中，我們討論遞迴式循環圖，$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.