### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 2212-2225 |

Number of pages | 14 |

Journal | International Journal of Computer Mathematics |

Volume | 87 |

Issue number | 10 |

DOIs | |

State | Published - 2010 |

### Keywords

- Hamiltonian cycle; bubble-sort networks; interconnection networks; mutually independent Hamiltonian cycles; Cayley graph

## Fingerprint Dive into the research topics of 'The construction of mutually independent Hamiltonian cycles in bubble-sort graphs'. Together they form a unique fingerprint.

## Cite this

Shih, Y-K., Lin, C-K., Frank Hsu, D., Tan, J-M., & Hsu, L-H. (2010). The construction of mutually independent Hamiltonian cycles in bubble-sort graphs.

*International Journal of Computer Mathematics*,*87*(10), 2212-2225. https://doi.org/10.1080/00207160802512700