Mutually Independent Hamiltonian Cycle of Burnt Pancake Graphs

概要

論文の詳細を見る
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 ui≠vi for 2≤i≤n. 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.
2011-07-01