publication . Article . 2009

Mutually independent hamiltonian cycles for the pancake graphs and the star graphs

Lin, Cheng-Kuan; Tan, Jimmy J.M.; Huang, Hua-Min; Hsu, D. Frank; Hsu, Lih-Hsing;
Open Access
  • Published: 01 Sep 2009 Journal: Discrete Mathematics, volume 309, pages 5,474-5,483 (issn: 0012-365X, Copyright policy)
  • Publisher: Elsevier BV
Abstract
AbstractA hamiltonian cycle C of a graph G is an ordered set 〈u1,u2,…,un(G),u1〉 of vertices such that ui≠uj for i≠j and ui is adjacent to ui+1 for every i∈{1,2,…,n(G)−1} and un(G) is adjacent to u1, where n(G) is the order of G. The vertex u1 is the starting vertex and ui is the ith vertex of C. Two hamiltonian cycles C1=〈u1,u2,…,un(G),u1〉 and C2=〈v1,v2,…,vn(G),v1〉 of G are independent if u1=v1 and ui≠vi for every i∈{2,3,…,n(G)}. 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 ex...
Subjects
free text keywords: Theoretical Computer Science, Discrete Mathematics and Combinatorics, Cayley graph, Cycle graph, Pairwise independence, Vertex (geometry), Hamiltonian path, symbols.namesake, symbols, Integer, Function composition, Discrete mathematics, Mathematics, Combinatorics, Star (graph theory), Hamiltonian, Pancake networks, Star networks
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue