Every semisymmetric graph is necessarily bipartite, with the two parts having equal size and the automorphism
group acting transitively on each of these parts. The numbers of regular bipartite
graphs on ,
2, ... nodes are 1, 2, 1, 3, 1, 4, 1, 6, 1, ... (OEIS A087114).
Folkman (1967) proved that there are no semisymmetric graphs of order , where is a prime number and constructed
some semisymmetric graphs of order , where and are primes and , including the so-called Folkman
graph. Folkman (1967) also asked if there exists a semisymmetric graph of order
30, which was subsequently answered in the negative by Ivanov (1987).
There are no semisymmetric graphs on fewer than 20 vertices (Skiena 1990, p. 186). Examples of semisymmetric graphs are illustrated above and summarized in the following table.
Bouwer, I. A. "On Edge But Not Vertex Transitive Regular Graphs." J. Combin. Th. Ser. B12, 32-40, 1972.Du,
S.-F. and Marus_ic_, D. "An Infinite Family of Biprimitive Semisymmetric Graphs."
J. Graph Th.32, 217-228, 1999.Du, S. and Xu, M. "A
Classification of Semisymmetric Graphs of Order ." Comm. Alg.28, 2685-2715, 2000.Folkman,
J. "Regular Line-Symmetric Graphs." J. Combin. Th.3, 215-232,
1967.House of Graphs. Semisymmetric Graphs. (4,8)-cage,
20-connected edge transitive graph
15, Folkman Graph, Gray
Graph, 110-Iofinova-Ivanov graph,
Ljubljana Graph, and Tutte
12 Cage.Iofinova, M. E. and Ivanov, A. A. "Bi-Primitive
Cubic Graphs." In Investigations
in Algebraic Theory of Combinatorial Objects. (Ed. I. A. Faradev,
A. A. Ivanov, M. H. Klin, and A. J. Woldar). Dordrecht,
Netherlands: Kluwer, pp. 459-472, 1994.Ivanov, A. V. "On
Edge But Not Vertex Transitive Regular Graphs." In Combinatorial
Design Theory (Ed. C. J. Colbourn and R. Mathon). Amsterdam,
Netherlands: North-Holland, pp. 273-285, 1987.Klin, M. H.
"On Edge But Not Vertex Transitive Graphs." In Algebraic
Methods in Graph Theory, Vol. I, II: Papers from the Conference held in Szeged,
August 24-31, 1978 (Ed. L. Lovász and V. T. Sós).
Amsterdam, Netherlands: North-Holland, pp. 399-403, 1981.Lipschutz,
S. and Xu, M.-Y. "Note on Infinite Families of Trivalent Semisymmetric Graphs."
European J. Combin.23, 707-711, 2002.Marušič,
D.; Pisanski, T.; and Wilson, S. "The Genus of the GRAY [sic] Graph is 7."
Europ. J. Combin.26, 377-385, 2005.Marušič,
D. and Potočnik, P. "Semisymmetry of Generalized Folkman Graphs."
European J. Combin.22, 333-349, 2001.Skiena, S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A087114
in "The On-Line Encyclopedia of Integer Sequences."