In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a semi-symmetric graph is an
undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
that is
edge-transitive
In geometry, a polytope (for example, a polygon or a polyhedron) or a Tessellation, tiling is isotoxal () or edge-transitive if its Symmetry, symmetries act Transitive group action, transitively on its Edge (geometry), edges. Informally, this mea ...
and
regular, but not
vertex-transitive
In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face i ...
. 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, and its
automorphism group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
must act
transitively 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 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
Folkman graph, 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
In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges. It is named after W. T. Tutte.
The Tutte 12-cage is the unique (3-12)- cage . It was discovered by C. T. Benson in ...
.
[.]
References
External links
*{{mathworld , urlname = SemisymmetricGraph , title = Semisymmetric Graph, mode=cs2
Algebraic graph theory
Graph families
Regular graphs