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 |