A condition of Hamiltonicity over Cayley digraphs on generalized dihedral groups

ADRIÁN PASTINE; DANIEL A JAUME

Tandil

Congreso; UMA 2010; 2010

Unión Matemática Argentina

The Cayley digraph on a group G with generating set S, denoted −−→Cay (G; S), is the digraph with vertex set G, and arc set containing an arc from g to gs whenever g ∈ G and s ∈ S (if we ask S = S −1 and e /∈ S, we have just a Cayley graph). Cayley (di)graphs of groups have been extensively studied and some interesting results have been obtained (see [3]). In particular, several authors have studied the following folk conjecture: every Cayley graph is Hamiltonian (see [4]). Another interesting problem is to characterize which Cayley digraphs have Hamiltonian paths. These problems tie together two seemingly unrelated concepts: traversability and symmetry on (di)graphs. Both problems had been attacked for more than fifty years (started with [5]), yet not much progress has been made and they remain open. Most of the results proved thus far depend on various restrictions made either on the class of groups dealt with or on the generating sets (for example one can easily see that Cayley graphs on Abelian groups have Hamilton cycles). The class of groups with cyclic commutator subgroups has attracted attention of many researchers (see [2]). And for many technical reasons the key to proving that every connected Cayley Graphs on a finite group with cyclic commutator subgroup has a Hamilton cycle very likely lies with dihedral groups. Given a finite abelian group H, the generalized dihedral group over H is DH = H, τ : τ 2 = e τhτ = h −1 ∀h ∈ H  Recently (2010) in [1], working on generalized dihedral groups, was proved that every Cayley graph on the dihedral group D2n with n even has a Hamilton cycle. We prove in this work, via a recursive algorithm, that if S ∩ H 6= ∅, then → Cay(DH, S) is Hamiltonian. Referencias [1] B. Alspach, C. C. Chen & M. Dean. Hamilton paths in Cayley graphs on generalized dihedral groups. ARS Mathematica Contemporanea 3(2010) 29- 47. [2] B. Alspach, & Zhang C-Q. Hamilton cycles in cubic Cayley graphs on dihedral groups. ARS Combinatorica 28(1989), pp.101-108. [3] N. Biggs, Algebraic Graph Theory. Cambridge University Press, Cambriedge, 1993. [4] S. J. Curran & J. A. Gallian. Hamiltonian cycles and paths in Cayley graphs and digraphs-A survey. Discrete Mathematics 156 (1996) 1-18. [5] E. Rapaport-Strasser. Cayley color groups and Hamilton lines. Scripta Math. 24 (1959) 51-58.