TOPICS

# Semisymmetric Graph

A regular graph that is edge-transitive but not vertex-transitive is called a semisymmetric graph (Marušič and Potočnik 2001). In contrast, any graph that is both edge-transitive and vertex-transitive is called a symmetric graph.

Note that it is possible for a graph to be edge-transitive yet neither vertex-transitive not regular. An example is the Pasch graph, which is therefore not semisymmetric. Other examples include the star graphs, rhombic dodecahedral graph, rhombic triacontahedral graph, and Schläfli double sixes graph.

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.

 graph 20 Folkman graph 54 Gray graph 64 (16,4)-Hadamard graph 80 (4,8)-cage graph 110 110-Iofinova-Ivanov graph 112 Ljubljana graph 126 Tutte 12-cage 182 182-Iofinova-Ivanov graph 288 Leonard graph 316 (6,8)-cage graph 506 506-Iofinova-Ivanov graph 800 (8,8)-cage graph 990 Ivanov-Ivanov-Faradjev graph 1640 (10,8)-cage graph 2730 (5,12)-cage graph 2928 (12,8)-cage graph 4760 (14,8)-cage graph

Cubic Semisymmetric Graph, Edge-Transitive Graph, Folkman Graph, Gray Graph, Iofinova-Ivanov Graphs, Ivanov-Ivanov-Faradjev Graph, Ljubljana Graph, Symmetric Graph, Vertex-Transitive Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Bouwer, I. A. "On Edge But Not Vertex Transitive Regular Graphs." J. Combin. Th. Ser. B 12, 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.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.Iofinova, M. E. and Ivanov, A. A. "Bi-Primitive Cubic Graphs." In Investigations in the Algebraic Theory of Combinatorial Objects. pp. 123-134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, pp. 137-152, 1985.)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. and Potočnik, P. "Semisymmetry of Generalized Folkman Graphs." European J. Combin. 22, 333-349, 2001.Marušič, D.; Pisanski, T.; and Wilson, S. "The Genus of the GRAY [sic] Graph is 7." Europ. J. Combin. 26, 377-385, 2005.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."

## Referenced on Wolfram|Alpha

Semisymmetric Graph

## Cite this as:

Weisstein, Eric W. "Semisymmetric Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SemisymmetricGraph.html