•   Wikis

# Half-transitive graph: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

# Encyclopedia

Updated live from Wikipedia, last check: May 19, 2013 03:12 UTC (51 seconds ago)

 Graph families defined by their automorphisms distance-transitive $\rightarrow$ distance-regular $\leftarrow$ strongly regular $\downarrow$ symmetric (arc-transitive) $\leftarrow$ t-transitive, t ≥ 2 $\downarrow$ (if connected) vertex- and edge-transitive $\rightarrow$ edge-transitive and regular $\rightarrow$ edge-transitive $\downarrow$ $\downarrow$ vertex-transitive $\rightarrow$ regular $\uparrow$ Cayley graph skew-symmetric

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.

The Holt graph 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,[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]

## References

1. ^ Gross, J.L. and Yellen, J. (2004). Handbook of Graph Theory. CRC Press. p. 491. ISBN 1584880902.
2. ^ Babai, L (1996), "Automorphism groups, isomorphism, reconstruction", in Graham, R; Groetschel, M; Lovasz, L, Handbook of Combinatorics, Elsevier
3. ^ Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.
4. ^ Biggs, Norman (1993). Algebraic Graph Theory (2nd ed. ed.). Cambridge: Cambridge University Press. ISBN 0-521-45897-8.
5. ^ Holt, Derek F. (1981), "A graph which is edge transitive but not arc transitive", Journal of Graph Theory 5 (2): 201–204, doi:10.1002/jgt.3190050210  .