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).

See also

Bicirculant Graph, Cayley Graph, Cyclic Group, Group Orbit, Haar Graph, Semiregular Group Action

Explore with Wolfram|Alpha

References

Chen, H. N.; Li, J. J.; Ma, J. C.; and Yu, H. "On Edge-Primitive -Arc-Transitive (Bi-)Cayley Graphs." Elec. J. Combin. 33, P4.28, 2026. https://doi.org/10.37236/15130.Feng, Y.-Q. and Zhou, J.-X. "Cubic Bi-Cayley Graphs over Abelian Groups." Europ. J. Combin. 36, 679-693, 2014.Pan, J. and Wu, C. "On Edge-Primitive Graphs of Order Twice a Prime Power." Disc. Math. 342, 111594, 2019. https://doi.org/10.1016/j.disc.2019.07.010.Singer, J. "A Theorem in Finite Projective Geometry and Some Applications to Number Theory." Trans. Amer. Math. Soc. 43, 377-385, 1938. https://doi.org/10.1090/S0002-9947-1938-1501951-4.

Cite this as:

Weisstein, Eric W. "Bi-Cayley Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Bi-CayleyGraph.html

Subject classifications