DocumentCode :
3445065
Title :
Mutually Independent Hamiltonianicity of Pancake Graphs and Star Graphs
Author :
Lin, Cheng-Kuan ; Tan, Jimmy J M ; Huang, Hua-Min ; Hsu, D. Frank ; Hsu, Lih-Hsing
Author_Institution :
Dept. of Comput. Sci., Nat. Chiao Tung Univ., Hsinchu
fYear :
2008
fDate :
7-9 May 2008
Firstpage :
151
Lastpage :
158
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 2008. I-SPAN 2008. International Symposium on
Conference_Location :
Sydney, NSW
ISSN :
1087-4089
Print_ISBN :
978-0-7695-3125-0
Type :
conf
DOI :
10.1109/I-SPAN.2008.41
Filename :
4520209
Link To Document :
بازگشت