Bi-Cayley Graph

A bi-Cayley graph over a group is a graph admitting a semiregular group action of by graph automorphisms with exactly two group orbits on its vertex set. Equivalently, for suitable subsets , a bi-Cayley graph is a graph that has vertices

with right edges whenever , left edges whenever , and spoke edges whenever . For a simple graph, the subsets and are inverse-closed (closed under taking inverse elements) and do not contain the identity element. The term semi-Cayley graph is sometimes used for the same notion.

When is a cyclic group, bi-Cayley graphs are bicirculant graphs. In particular, the bi-Cayley graphs over cyclic groups with both orbits independent are the Haar graphs.

The Levi graph of the finite projective plane has 26 vertices, each of vertex degree 4. A cyclic group of order 13 generated by a Singer cycle acts regularly on the points and on the lines (Singer 1938). The two group orbits are the parts of the bipartite graph, each an independent vertex set, so . Pan and Wu (2019) show that the graph is edge-primitive and 4-arc-transitive, hence also 2-arc-transitive. Edge-primitivity means that the full graph automorphism group has a primitive group action on the edges.

Thus the Levi graph of meets the hypotheses of Theorem 1 of Chen et al. (2026) under their bipartite bi-Cayley convention, but the list contains no bipartite graph with both 26 vertices and vertex degree 4. For instance, the listed Heawood graph, the Levi graph of , has only 14 vertices. The only listed complete bipartite graph on 26 vertices is , of vertex degree 13. Example 14 also has 26 vertices, but its vertex degree is 9. None of Examples 14-18 has vertex degree 4. In the projective nonincidence case, the graph on points and hyperplanes of a finite projective space with has degree . Degree 4 therefore occurs only for , whose nonincidence graph has 14 vertices (Pan and Wu 2019).