In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a semi-symmetric graph is an undirected graph that is edge-transitive

Edge-transitive graph

In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is anautomorphism of G that maps e1 to e2....

 and regular

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

, but not vertex-transitive

Vertex-transitive graph

In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...

.

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

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

, and its automorphism group

Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....

 must act transitively on each of the two vertex sets of the bipartition. In the diagram on the right, green vertices can not be mapped to red ones by any automorphism.

Semi-symmetric graphs were first studied by Jon Folkman

Jon Folkman

Jon Hal Folkman was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation.-Schooling:Folkman was a Putnam Fellow in 1960. He received his Ph.D...

 in 1967, who discovered the smallest semi-symmetric graph, the Folkman graph

Folkman graph

In the mathematical field of graph theory, the Folkman graph, named after Jon Folkman, is a bipartite 4-regular graph with 20 vertices and 40 edges....

 on 20 vertices.

The smallest cubic

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....

 semi-symmetric graph is the Gray graph

Gray graph

In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 , then discovered independently by Bouwer 1968 in reply to a question...

 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č

Dragan Marušic

Dragan Marušič is a Slovene mathematician.His research focuses on topics in algebraic graph theory, particularly the symmetry of graphs and the action of finite groups on combinatorial objects. In 2002, he helped show that the Gray graph is the smallest cubic semi-symmetric graph, resolving a...

 and Aleksander Malnič.

All the cubic semi-symmetric graphs on up to 768 vertices are known. According to Conder, Malnič, Marušič and Potočnik, the four smallest possible cubic semi-symmetric graph after the Gray graph are the Iofinova–Ivanov graph on 110 vertices, the Ljubljana graph

Ljubljana graph

In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.It is a cubic graph with diameter 8, radius 7, chromatic number 2 and chromatic index 3. Its girth is 10 and there are exactly 168 cycles of length 10 in it...

 on 112 vertices, a graph on 120 vertices with girth 8 and the Tutte 12-cage

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 named after W. T. Tutte....

.