Cayley graphs and \(G\)-graphs: some applications (Q651882)

Let \(G\) be a group and \(S\) a set of generators of \(G\). The \(G\)-graph \(\Phi(G;S)\) is constructed as follows: The vertices of \(\Phi(G;S)\) are the distinct (right) cosets of the cyclic subgroups generated by the elements of \(S\) and two such vertices are adjacent if the right cosest they represent have non-empty intersection. The graph obtained from \(\Phi(G;S)\) by deleting all loops is also called a \(G\)-graph and is denoted by \({\overline{\Phi}}(G;S)\). The authors establish a sufficient condition for a \(G\)-graph \({\overline{\Phi}}(G;S)\) to be a Cayley graph. They use this connection of \(G\)-graphs with Cayley graphs to determine new classes of Cayley graphs that are hamiltonian.