有錯偶蝴蝶圖中漢彌爾頓環路之嵌入

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.