Semi-symmetric graph

The Folkman graph, the smallest semi-symmetric graph.

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	t-transitive, t ≥ 2		skew-symmetric
↓
(if connected) vertex- and edge-transitive	→	edge-transitive and regular	→	edge-transitive
↓		↓		↓
vertex-transitive	→	regular	→	(if bipartite) biregular
↑
Cayley graph	←	zero-symmetric		asymmetric

In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive.

In other words, a graph is semi-symmetric if each vertex has the same number of incident edges, and there is a symmetry taking any of its edges to any other of its edges, but there is some pair of vertices that cannot be mapped into each other by a symmetry. A semi-symmetric graph must be bipartite, and its automorphism group must act transitively on each of the two vertex sets of the bipartition. In the diagram on the right, green vertices can not be mapped to red ones by any automorphism.

Semi-symmetric graphs were first studied by Folkman (1967), who discovered the smallest semi-symmetric graph, the Folkman graph on 20 vertices. The smallest cubic semi-symmetric graph is the Gray graph on 54 vertices. A complete list of cubic semi-symmetric graphs on at most 768 vertices is given by Conder et al. (2006).

References

• Bouwer, I. Z. (1968), "An edge but not vertex transitive cubic graph", Bulletin of the Canadian Mathematical Society, 11: 533–535.

• Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), "A census of semisymmetric cubic graphs on up to 768 vertices", Journal of Algebraic Combinatorics, 23: 255–294, doi:10.1007/s10801-006-7397-3.

• Folkman, J. (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory, 3: 215–232, doi:10.1016/S0021-9800(67)80069-3.

External links

• Weisstein, Eric W. "Semisymmetric Graph". MathWorld.