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