Connected graphs as subgraphs of Cayley graphs: Conditions on Hamiltonicity

Let ΓΓ be a connected simple graph, let V(Γ)V(Γ) and E(Γ)E(Γ) denote the vertex-set and the edge-set of ΓΓ, respectively, and let n=|V(Γ)|n=|V(Γ)|. For 1≤i≤n1≤i≤n, let eiei be the element of elementary abelian group Z2n which has 1 in the iith coordinate, and 0 in all other coordinates. Assume that V(Γ)={ei∣1≤i≤n}V(Γ)={ei∣1≤i≤n}. We define a set ΩΩ by Ω={ei+ej∣{ei,ej}∈E(Γ)}Ω={ei+ej∣{ei,ej}∈E(Γ)}, and let CayΓCayΓ denote the Cayley graph over Z2n with respect to ΩΩ. It turns out that CayΓCayΓ contains ΓΓ as an isometric subgraph. In this paper, the relations between the spectra of ΓΓ and CayΓCayΓ are discussed. Some conditions on the existence of Hamilton paths and cycles in ΓΓ are obtained.