Semi-symmetric graph

From Wikipedia, the free encyclopedia

The Folkman graph, the smallest semi-symmetric graph.

In mathematics, 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.

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.^[1] A complete list of cubic semi-symmetric graphs on at most 768 vertices is given by Conder et al. (2006).

[edit] Notes

^ The Gray graph was first observed to be semi-symmetric by Bouwer (1968). It was proven to be the smallest cubic semi-symmetric graph by Dragan Marušič and Aleksander Malnič.

[edit] 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 .