Circuits on directed grids (Q1178185)

This article is a survey of the results obtained by the author and a succession of undergraduate students participating in summer research programs over period of eight summers. Suppose \(G\) is any group and \(S\) is a set of generators of \(G\). The digraph \(\text{Cay}(S:G)\) is defined as follows. 1. The elements of \(G\) are the vertices of \(\text{Cay}(S:G)\). 2. For \(x\) and \(y\) in \(G\), there is an arc from \(x\) to \(y\) if and only if \(xs=y\) for some \(s\) in \(S\). The following are two examples of the results obtained. Suppose \(C=\text{Cay}(\{1,0),(0,1)\}:Z_ m\times Z_ n)\). 1. \(C\) has a closed walk passing through one vertex exactly twice and all others exactly once if and only if there are positive integers \(a\) and \(b\) such that \(am+bn=mn+1\) and \(\gcd(a,b)\leq 2\). 2. \(C\) can be decomposed into two disjoint Hamiltonian circuits if and only if there exists positive integer \(u\) and \(v\) such that \(u+v=\gcd(m,n)\) and \(\gcd(uv,mn)=1\).