Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey

DOI10.1016/0012-365X(95)00072-5zbMath0857.05067MaRDI QIDQ1923505

Joseph A. Gallian, Stephen J. Curran

Publication date: 12 November 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Cayley graphCayley digraphHamilton cycleHamilton pathsHamilton circuits

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (48)

Cayley graphs of order 6pq and 7pq are Hamiltonian ⋮ Hamiltonian problems in directed graphs with simple row patterns ⋮ Parameters of the coprime graph of a group ⋮ Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes ⋮ Absorption Cayley graph ⋮ On Hamilton cycle decomposition of 6-regular circulant graphs ⋮ Heuristic search for Hamilton cycles in cubic graphs ⋮ Unnamed Item ⋮ Two Sufficient Conditions for Vertex-transitive Hamilton Graphs of Prime-power Order ⋮ Hamilton decompositions of 6-regular Cayley graphs on even abelian groups with involution-free connections sets ⋮ Hamilton circuits in the directed wrapped Butterfly network ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ Unnamed Item ⋮ Dead ends on wreath products and lamplighter groups ⋮ Hamilton cycles in dense vertex-transitive graphs ⋮ Hamiltonian cycles in Cayley graphs of imprimitive complex reflection groups ⋮ Fault-free mutually independent Hamiltonian cycles of faulty star graphs ⋮ Resolving the Hamiltonian problem for vertex-transitive graphs of order a product of two primes ⋮ Some problems on Cayley graphs ⋮ Further results on the enumeration of Hamilton paths in Cayley digraphs on semidirect products of cyclic groups ⋮ Hamiltonicity of vertex-transitive graphs of order 4\(p\) ⋮ Cayley graphs of order \(30p\) are Hamiltonian ⋮ Hamiltonian cycles in cubic Cayley graphs: The \(\langle 2,4k,3\rangle \) case ⋮ Hamiltonicity of digraphs for universal cycles of permutations ⋮ On groups with the Lohse property. ⋮ Long cycles and paths in distance graphs ⋮ Hamilton-connected Cayley graphs on Hamiltonian groups ⋮ Hamilton decompositions of certain 6-regular Cayley graphs on abelian groups with a cyclic subgroup of index two ⋮ The construction of mutually independent Hamiltonian cycles in bubble-sort graphs ⋮ Some Topics in Graph Theory ⋮ Hamiltonian paths for involutions in the square of a Cayley graph ⋮ Hamiltonian cycles in covering graphs of trees ⋮ On the structure of Hamiltonian cycles in Cayley graphs of finite quotients of the modular group ⋮ Hamilton cycles in primitive vertex-transitive graphs of order a product of two primes – the case PSL(2, q^2) acting on cosets of PGL(2, q) ⋮ A survey on Hamiltonicity in Cayley graphs and digraphs on different groups ⋮ Connected graphs as subgraphs of Cayley graphs: conditions on hamiltonicity ⋮ On hamiltonicity of circulant digraphs of outdegree three ⋮ Hamilton paths and cycles in vertex-transitive graphs of order \(6p\) ⋮ Mutually independent Hamiltonian cycles for the pancake graphs and the star graphs ⋮ Hamilton cycles and paths in vertex-transitive graphs-current directions ⋮ Hamiltonian paths in Cayley graphs ⋮ 6-regular Cayley graphs on abelian groups of odd order are Hamiltonian decomposable ⋮ Combinatorial families that are exponentially far from being listable in Gray code sequence ⋮ On endo-Cayley digraphs: the Hamiltonian property ⋮ Miscellaneous Digraph Classes ⋮ Automorphism groups with cyclic commutator subgroup and Hamilton cycles ⋮ Dynamical decoupling schemes derived from Hamilton cycles ⋮ Hamiltonian cycles of power graph of abelian groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cayley digraphs and (1,j,n)-sequencings of the alternating groups \(A_ n\)
• Cayley digraphs of prime-power order are hamiltonian
• Lifting Hamilton cycles of quotient graphs
• Hamiltonian paths in Cayley digraphs of finitely-generated infinite Abelian groups
• Hamiltonian circuits in Cayley graphs
• Connected Cayley graphs of semi-direct products of cyclic groups of prime order by Abelian groups are Hamiltonian
• Cycles in graphs. (Workshop Cycles in Graphs held at Simon Fraser University, Burnaby, British Columbia, Canada, July 5 - August 20, 1982)
• Infinite Hamiltonian paths in Cayley digraphs
• Hamiltonian decomposition of Cayley graphs of degree 4
• On Hamiltonian cycles in Cayley graphs of wreath products
• On edge-Hamiltonian property of Cayley graphs
• A Hamilton cycle in the Cayley graph of the \(\langle 2,p,3 \rangle\) presentation of PSL\(_ 2(p)\)
• On hamiltonian circuits in Cayley diagrams
• Enumeration of Hamiltonian paths in Cayley diagrams
• Hamilton decompositions of Cartesian products of graphs
• Arrangement graphs: A class of generalized star graphs
• A method and two algorithms on the theory of partitions
• Paths and circuits in finite groups
• Vertex-primitive digraphs of prime-power order are hamiltonian
• Hamiltonian decompositions of Cayley graphs on Abelian groups
• Two edge-disjoint hamiltonian cycles in the butterfly graph
• Determining the Hamilton-connectedness of certain vertex-transitive graphs
• Hamilton-connected derangement graphs on \(S_ n\)
• The Hamiltonicity of directed \(\sigma\)-\(\tau\) Cayley graphs (Or: A tale of backtracking)
• Hamilton paths in Cayley digraphs of metacyclic groups
• Pseudo-Cartesian products and Hamiltonian decompositions of Cayley graphs on abelian groups
• Gray codes for reflection groups
• Infinite Hamiltonian paths in Cayley digraphs of hyperbolic symmetry groups
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Hamiltonian Checkerboards
• Circuits in cayley digraphs of finite abelian groups
• Group Action Graphs and Parallel Architectures
• When the cartesian product of two directed cycles is hypo-Hamiltonian
• When the cartesian product of two directed cycles is hyperhamiltonian
• Ringing the Cosets
• Generalized hamiltonian circuits in the cartesian product of two-directed cycles
• Hamiltonian Decompositions of Graphs, Directed Graphs and Hypergraphs
• When the cartesian product of directed cycles is Hamiltonian
• Doubly adjacent gray codes for the symmetric group
• Disjoint circuits in the cartesian product of two directed cycles
• Hamilton cycles and paths in butterfly graphs
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• A new class of interconnection networks based on the alternating group
• A survey: Hamiltonian cycles in Cayley graphs
• Hamiltonian decompositions of products of cycles

This page was built for publication: Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey