half-transitive graph

{{Short description|Type of graph in graph theory}}

{{Graph families defined by their automorphisms}}

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.{{cite book |author1=Gross, J.L. |author2=Yellen, J. | title=Handbook of Graph Theory | publisher=CRC Press | year=2004| page=491 | isbn=1-58488-090-2}} 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.

File:Holt graph.svg is the smallest half-transitive graph. The lack of reflectional symmetry in this drawing highlights the fact that edges are not equivalent to their inverse.]]

Every connected symmetric graph must be vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree,{{Cite book | first = L | last = Babai | editor-last = Graham | editor-first = R | editor2-last = Grötschel | editor2-first = M | editor2-link = Martin Grötschel | editor3-last = Lovász | editor3-first = L | title = Handbook of Combinatorics | contribution = Automorphism groups, isomorphism, reconstruction | contribution-url = http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps | year = 1996 | publisher = Elsevier | access-date = 2009-09-05 | archive-date = 2010-06-11 | archive-url = https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps | url-status = dead }} so that half-transitive graphs of odd degree do not exist. However, there do exist half-transitive graphs of even degree.{{cite journal | last=Bouwer | first=Z. |title=Vertex and Edge Transitive, But Not 1-Transitive Graphs | journal=Canadian Mathematical Bulletin | volume=13 | pages=231–237 | date=1970 | doi=10.4153/CMB-1970-047-8 | doi-access=free}} The smallest half-transitive graph is the Holt graph, with degree 4 and 27 vertices.{{cite book | author=Biggs, Norman | title=Algebraic Graph Theory | edition=2nd | location=Cambridge | publisher=Cambridge University Press | year=1993 | isbn=0-521-45897-8}}{{Cite journal|title=A graph which is edge transitive but not arc transitive|first=Derek F.|last=Holt|journal=Journal of Graph Theory|volume=5|issue=2|pages=201–204|year=1981|doi=10.1002/jgt.3190050210}}.