Author :
Lin, Cheng-Kuan ; Tan, Jimmy J M ; Huang, Hua-Min ; Hsu, D. Frank ; Hsu, Lih-Hsing
Abstract :
A hamiltonian cycle C of a graph G is described as langu1, u2,..., un(G), u1rang to emphasize the order of vertices in C. Thus, u1 is the start vertex and ui is the i-th vertex in C. Two hamiltonian cycles of G start at a vertex x, C1 = langu1, u2,..., un(G), u1rang and C2 = langv1, v2,..., vn(G), v1rang, are independent if x = u1 = v1 and u1 ne vi for every i, 2 les i les n(G). A set of hamiltonian cycles {C1, C2,..., Ck} of G are mutually independent if any two different hamiltonian cycles are independent. The mutually independent hamiltonicity of graph G, IHC(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent hamiltonian cycles ofG starting at u. Inthispaper, we are going to study IHC(G) for the n-dimensional pancake graph Pn and the n-dimensional star graph Sn. We prove that IHC(Pn) = n - 1 if n ges 4 and IHC(Sn) = n-1 if nges5.
Keywords :
graph theory; hamiltonian cycle; mutually independent hamiltonianicity; n- dimensional pancake graph; n-dimensional star graph; Computer networks; Computer science; Concurrent computing; Contracts; Councils; Information science; Mathematics; Parallel architectures; Tin; hamiltonian; mutually independent hamiltonianicity; pancake graph; star graph;
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 2008. I-SPAN 2008. International Symposium on