Mutually Independent Hamiltonian Cycle of Burnt Pancake Graphs

Yung-Ling LAI  Da-Chung YU  Lih-Hsing HSU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.7   pp.1553-1557
Publication Date: 2011/07/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.1553
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
burnt pancake graph,  hamiltonian cycle,  mutually independent,  

Full Text: PDF>>
Buy this Article

Let G=(V,E) be a graph of order n. A Hamiltonian cycle of G is a cycle that contains every vertex in G. Two Hamiltonian cycles C1=<u1, u2, , un, u1> and C2=<v1, v2, , vn, v1> of G are independent if u1=v1 and uivi for 2 ≤ in. A set of Hamiltonian cycles {C1, C2, , Ck} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph G is the maximum integer k such that for any vertex u of G there are k mutually independent Hamiltonian cycles of G starting at u. For the n-dimensional burnt pancake graph Bn, this paper proved that IHC(B2)=1 and IHC(Bn)=n for n ≥ 3.