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 the graph's edges to any other of its edges, but there is some pair of vertices such that no symmetry maps the first into the second.

Properties

A semi-symmetric graph must be

bipartite Bipartite may refer to: * 2 (number) * Bipartite (theology), a philosophical term describing the human duality of body and soul * Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...

, and its automorphism group must act

transitively Transitivity or transitive may refer to: Grammar * Transitivity (grammar), a property of verbs that relates to whether a verb can take direct objects * Transitive verb, a verb which takes an object * Transitive case, a grammatical case to mark a ...

on each of the two vertex sets of the bipartition (in fact, regularity is not required for this property to hold). For instance, in the diagram of the

Folkman graph Folkman may refer to: People * Jens Christian Folkman Schaanning, a Norwegian politician * Jon Folkman, an American mathematician * Judah Folkman, an American medical scientist * Roy Folkman, an Israeli politician Math * Folkman graph, a type of ...

shown here, green vertices can not be mapped to red ones by any automorphism, but every two vertices of the same color are symmetric with each other.

History

Semi-symmetric graphs were first studied E. Dauber, a student of F. Harary, in a paper, no longer available, titled "On line- but not point-symmetric graphs". This was seen by Jon Folkman, whose paper, published in 1967, includes the smallest semi-symmetric graph, now known as the

, on 20 vertices. The term "semi-symmetric" was first used by Klin ''et al.'' in a paper they published in 1978.

Cubic graphs

The smallest

cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...

semi-symmetric graph (that is, one in which each vertex is incident to exactly three edges) is the Gray graph on 54 vertices. It was first observed to be semi-symmetric by . It was proven to be the smallest cubic semi-symmetric graph by Dragan Marušič and Aleksander Malnič. All the cubic semi-symmetric graphs on up to 10000 vertices are known. According to Conder, Malnič, Marušič and Potočnik, the four smallest possible cubic semi-symmetric graphs after the Gray graph are the Iofinova–Ivanov graph on 110 vertices, the Ljubljana graph on 112 vertices,. a graph on 120 vertices with girth 8 and the Tutte 12-cage..

References

External links

*{{mathworld , urlname = SemisymmetricGraph , title = Semisymmetric Graph Algebraic graph theory Graph families Regular graphs