(Prior to publication, this paper should be cited as arXiv:0706.1567.)

We study bipartite graphs  Γ  between sets  A  and  B  of  n  vertices, such that some cyclic order-n  group  G  of automorphisms of  Γ  acts transitively on both  A  and  B . By identifying  A  and  B  with  Z/nZ  in such a way that a generator of  G  maps  i → i +1,  we can identify such a graph with the subset  S  of  Z/nZ  corresponding to vertices in  B  connected to vertex  0  in  A.  It is easy to show that the graph corresponding to  S  is isomorphic to the graph corresponding to  cS + d  for any integers  c, d  with  c  coprime to  n . We show that, conversely, if the graphs corresponding to subsets  S  and  T  of  Z/nZ  are isomorphic, and  #S ≤3,  then  T = cS + d  for some  c  and  d . We give examples showing this result is not always true for larger sets  S,  as well as results results showing it continues to hold in some situations.

Our graphs are bipartite analogues of the much-studied class of circulant graphs. The isomorphism problem for such graphs has been studied by many authors, culminating in a magnificent solution by Muzychuk. Our results are a first step towards a bipartite analogue of Muzychuk's result.

Michael Zieve:  home page   publication list