Title: | 有錯偶蝴蝶圖中漢彌爾頓環路之嵌入 Hamiltonian Cycles of Even Butterfly Graph with Two Adjacent Pair Node Fault |
Authors: | 楊明堅 Ming-Jeng Yang 徐力行 譚健民 Lih-Hsing Hsu Jimmy J.M. Tan 資訊科學與工程研究所 |
Keywords: | 漢彌爾頓環路;kp-漢彌爾頓;環繞蝴蝶圖;環路嵌入;凱力圖;hamiltonian cycles;kp-hamiltonian;wrapped butterfly;cycle embedding;Cayley graph |
Issue Date: | 2000 |
Abstract: | 由Leighton所定義的環繞蝴蝶圖BFn有許多好的性質,包括規律性, 對稱性, 對數直徑, 最大連結性, 漢彌爾頓, 漢彌爾頓分解, 等。我 們討論有錯環繞偶蝴蝶圖BFn中漢彌爾頓環路的嵌入, 當BFn是雙 邊圖的時候。因為環繞偶蝴蝶圖BFn是雙邊圖若且唯若n是偶數, 我們證明當n是大於或等於6的情況下, BFn是2ap-漢彌爾頓。 The wrapped butterfly network BFn defined by Leighton has a lot of good properties including regularity, symmetry, logarithmic diameter, maximal connectivity, hamiltonian, hamiltonian decomposable, etc. We study cycle embedding in a faulty wrapped butterfly BFn when BFn is a bipartite graph. Since BFn is bipartite if and only if n is even, we prove that the graph BFn is 2ap-hamiltonian if n is an even integer with n > 4. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#NT890394045 http://hdl.handle.net/11536/66948 |
Appears in Collections: | Thesis |