The Full Wiki



More info on Half-transitive graph

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)

From Wikipedia, the free encyclopedia

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, http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps  
  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  .







Got something to say? Make a comment.
Your name
Your email address
Message