標題: The construction of mutually independent Hamiltonian cycles in bubble-sort graphs
作者: Shih, Yuan-Kang
Lin, Cheng-Kuan
Hsu, D. Frank
Tan, Jimmy J. M.
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
關鍵字: Hamiltonian cycle;bubble-sort networks;interconnection networks;mutually independent Hamiltonian cycles;Cayley graph
公開日期: 2010
摘要: A Hamiltonian cycle C=< u(1), u(2), ..., u(n(G)), u(1) > with n(G)=number of vertices of G, is a cycle C(u(1); G), where u(1) is the beginning and ending vertex and u(i) is the ith vertex in C and u(i)not equal u(j) for any i not equal j, 1 <= i, j <= n(G). A set of Hamiltonian cycles {C(1), C(2), ..., C(K)} of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B(n))=n-1 if n >= 4, where B(n) is the n-dimensional bubble-sort graph.
URI: http://hdl.handle.net/11536/5992
http://dx.doi.org/10.1080/00207160802512700
ISSN: 0020-7160
DOI: 10.1080/00207160802512700
期刊: INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Volume: 87
Issue: 10
起始頁: 2212
結束頁: 2225
顯示於類別:期刊論文


文件中的檔案:

  1. 000281320400006.pdf