A bicirculant graph is a graph whose automorphism group contains an element with exactly two group orbits
of equal size on the vertex set. Equivalently, a graph
on 
vertices is an 
-bicirculant
if its vertices can be labeled
 |
so that the permutation sending 
to 
and 
to 
, where subscripts are taken mod 
, is an automorphism of the
graph. Edges may occur within either orbit or between the two orbits, provided they
are invariant under this simultaneous cyclic shift.
Bicirculant graphs are the bi-Cayley graphs over cyclic groups. Some authors use the hyphenated spelling bi-circulant. In the broader terminology, a bi-Cayley graph may use an arbitrary semiregular group action by graph automorphisms with two group orbits (Feng and Zhou 2014).
A bicirculant graph is therefore not the same thing as a bipartite circulant graph. For example, the Petersen graph is a 5-bicirculant under the order-5 rotation in its usual generalized Petersen graph drawing, but is not bipartite. Every circulant graph on an even number of vertices is bicirculant; in particular, every even-order complete graph, cycle graph, or empty graph is bicirculant. However, bicirculant graphs need not be bipartite and need not be circulant. No graph with an odd number of vertices is bicirculant. Standard bicirculant graph families include the generalized Petersen graphs, prism graphs, and ladder rung graphs.
Among trees, the only bicirculant examples are the path graphs 
and 
.
A graph automorphism of a tree preserves its
graph center. Thus, a bicirculant graph
automorphism of a tree on more than four vertices would either have a fixed
point at a central graph vertex or preserve a
central graph edge. In the latter case, the endpoint
orbit has length at most 2, contradicting the required two equal-length cyclic orbits.
The bicirculant graphs whose two cyclic orbits are both independent vertex sets are precisely the Haar graphs.
