Half-transitive graph explained

In the mathematical field of graph theory, a half-transitive graph is a graph that is both vertex-transitive and edge-transitive, but not symmetric.^[1] In other words, a graph is half-transitive if its automorphism group acts transitively upon both its vertices and its edges, but not on ordered pairs of linked vertices.

Every connected symmetric graph must be vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree,^[2] so that half-transitive graphs of odd degree do not exist. However, there do exist half-transitive graphs of even degree.^[3] The smallest half-transitive graph is the Holt graph, with degree 4 and 27 vertices.^{[4] [5]}

Notes and References

1. Book: Gross, J.L. . Yellen, J. . Handbook of Graph Theory . CRC Press . 2004. 491 . 1-58488-090-2.
2. Book: Babai, L . Graham . R . Grötschel . M . Martin Grötschel . Lovász . L . Handbook of Combinatorics . Automorphism groups, isomorphism, reconstruction . http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps . 1996 . Elsevier . 2009-09-05 . 2010-06-11 . https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps . dead .
3. Bouwer . Z. . Vertex and Edge Transitive, But Not 1-Transitive Graphs . . 13 . 231 - 237 . 1970 . 10.4153/CMB-1970-047-8 . free.
4. Book: Biggs, Norman . Algebraic Graph Theory . 2nd . Cambridge . Cambridge University Press . 1993 . 0-521-45897-8.
5. A graph which is edge transitive but not arc transitive. Derek F.. Holt. Journal of Graph Theory. 5. 2. 201–204. 1981. 10.1002/jgt.3190050210. .