TOPICS
Search

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 n=1, 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 2p, where p is a prime number and constructed some semisymmetric graphs of order 2pq, where p and q are primes and p=1 (mod q), 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).

SemisymmetricGraphs

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.


See also

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

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 2pq." 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

Subject classifications