Semi-symmetric graph
From Wikipedia, the free encyclopedia
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:.
- Folkman, J. (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory 3: 215–232, doi:.
.svg){kind=small}
