World Library  
Flag as Inappropriate
Email this Article

Vertex-transitive graph

Article Id: WHEBN0000581175
Reproduction Date:

Title: Vertex-transitive graph  
Author: World Heritage Encyclopedia
Language: English
Subject: Edge-transitive graph, Cayley graph, Lovász conjecture, Half-transitive graph, Biregular graph
Collection: Algebraic Graph Theory, Graph Families, Regular Graphs
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Vertex-transitive graph

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

In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphism

f:V(G) \rightarrow V(G)\

such that

f(v_1) = v_2.\

In other words, a graph is vertex-transitive if its automorphism group acts transitively upon its vertices.[1] A graph is vertex-transitive if and only if its graph complement is, since the group actions are identical.

Every symmetric graph without isolated vertices is vertex-transitive, and every vertex-transitive graph is regular. However, not all vertex-transitive graphs are symmetric (for example, the edges of the truncated tetrahedron), and not all regular graphs are vertex-transitive (for example, the Frucht graph and Tietze's graph).

Contents

  • Finite examples 1
  • Properties 2
  • Infinite examples 3
  • See also 4
  • References 5
  • External links 6

Finite examples

The edges of the truncated tetrahedron form a vertex-transitive graph (also a Cayley graph) which is not symmetric.

Finite vertex-transitive graphs include the symmetric graphs (such as the Petersen graph, the Heawood graph and the vertices and edges of the Platonic solids). The finite Cayley graphs (such as cube-connected cycles) are also vertex-transitive, as are the vertices and edges of the Archimedean solids (though only two of these are symmetric). Potočnik, Spiga and Verret have constructed a census of all connected cubic vertex-transitive graphs on at most 1280 vertices.[2]

Although every Cayley graph is vertex-transitive, there exist other vertex-transitive graphs that are not Cayley graphs. The most famous example is the Petersen graph, but others can be constructed including the line graphs of edge-transitive non-bipartite graphs with odd vertex degrees.[3]

Properties

The edge-connectivity of a vertex-transitive graph is equal to the degree d, while the vertex-connectivity will be at least 2(d+1)/3.[4] If the degree is 4 or less, or the graph is also edge-transitive, or the graph is a minimal Cayley graph, then the vertex-connectivity will also be equal to d.[5]

Infinite examples

Infinite vertex-transitive graphs include:

Two countable vertex-transitive graphs are called quasi-isometric if the ratio of their distance functions is bounded from below and from above. A well known conjecture stated that every infinite vertex-transitive graph is quasi-isometric to a Cayley graph. A counterexample was proposed by Diestel and Leader in 2001.[6] In 2005, Eskin, Fisher, and Whyte confirmed the counterexample.[7]

See also

References

  1. ^  .
  2. ^ Potočnik P., Spiga P. and Verret G. (2013), "Cubic vertex-transitive graphs on up to 1280 vertices", Journal of Symbolic Computation 50: 465–477,  .
  3. ^ Lauri, Josef; Scapellato, Raffaele (2003), Topics in graph automorphisms and reconstruction, London Mathematical Society Student Texts 54, Cambridge: Cambridge University Press, p. 44,  . Lauri and Scapelleto credit this construction to Mark Watkins.
  4. ^ Godsil, C. and Royle, G. (2001), Algebraic Graph Theory, Springer Verlag 
  5. ^ Babai, L. (1996), Technical Report TR-94-10, University of Chicago [2]
  6. ^ Diestel, Reinhard;  .
  7. ^ Eskin, Alex; Fisher, David; Whyte, Kevin (2005). "Quasi-isometries and rigidity of solvable groups".  .

External links

  • Weisstein, Eric W., "Vertex-transitive graph", MathWorld.
  • A census of small connected cubic vertex-transitive graphs . Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.