A semisymmetric graph is an undirected edge-transitive regular graph that is not vertex-transitive . In other words, a graph is semisymmetric if each vertex has the same number of incident edges and for each pair of edges there is symmetry that translates one edge to another, but there is some pair of vertices for which there is no symmetry that translates one vertex to another.
Content
Properties
A semisymmetric graph must be bipartite , and its automorphism group must act transitively on each of the two shares of the vertices of the bipartite graph. For example, in the Folkman graph shown in the diagram, green vertices cannot be mapped to red by any automorphism, but any two vertices of the same color are symmetrical with respect to each other.
History
Semisymmetric graphs were first studied by Dauber, a student of Frank Harari , in a now inaccessible article titled “On line-but not point-symmetric graphs” (On edge-but not vertex-symmetric graphs). The article was seen by John Folkman, whose article, published in 1967, included the smallest semisymmetric graph, now known as the Folkman Graph , with 20 vertices [1] . The term “semisymmetric” was first used by Klin, Lauri, and Ziv-Av in an article that they published in 1978 [2] .
Cubic Counts
The smallest cubic semisymmetric graph (that is, a graph in which each vertex is incident to exactly three edges) is a Gray graph with 54 vertices. The first to discover that the graph is semisymmetric, Bouver [3] . The fact that the graph is the smallest among cubic semisymmetric graphs was proved by Marushich and Malnich [4] .
All cubic semisymmetric graphs up to 768 vertices are known. According to Conder, Malnich, Marushich, and Potochnik, the four smallest cubic semi-symmetric graphs after the Gray graph are the Ivanov – Iofinova graph with 110 vertices , the Ljubljana graph with 112 vertices [5] , the graph with 120 vertices and the girth of 8 and 12 Tatt cells [6] .
Notes
- ↑ Folkman, 1967 , p. 215–232.
- ↑ Klin, Lauri, Ziv-Av, 2011 .
- ↑ Bouwer, 1968 .
- ↑ Bouwer, 1968 , p. 533-535.
- ↑ Conder, Malnič, Marušič, Pisanski, Potočnik, 2002 .
- ↑ Conder, Malnič, Marušič, Potočnik, 2006 , p. 255–294.
Literature
- Jon Folkman. Regular line-symmetric graphs // Journal of Combinatorial Theory. - 1967. - T. 3 , no. 3 - DOI : 10.1016 / S0021-9800 (67) 80069-3 .
- Mikhail Klin, Josef Lauri, Matan Ziv-Av. Links between two semisymmetric graphs on 112 vertices through the lens of association schemes . - 2011.
- Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. A census of semisymmetric cubic graphs on up to 768 vertices // Journal of Algebraic Combinatorics. - 2006 .-- T. 23 . - S. 255–294 . - DOI : 10.1007 / s10801-006-7397-3 .
- Bouwer IZ An Edge But Not Vertex Transitive Regular Graph // Bulletin of the Canadian Mathematical Society. - 1968. - T. 111968 , no. 12 - DOI : 10.4153 / CMB-1968-063-0 .
- Conder M., Malnič A., Marušič D., Pisanski T., Potočnik P. The Ljubljana Graph // IMFM Preprints. - Ljubljana: Institute of Mathematics, Physics and Mechanics, 2002 .-- V. 40 , no. 845 .
Links
- Weisstein, Eric W. Semisymmetric Graph on Wolfram MathWorld .