Editing Vertex-transitive graph

{{Short description|Graph where all pairs of vertices are automorphic}}
{{Graph families defined by their automorphisms}}

In the [[mathematics|mathematical]] field of [[graph theory]], an [[Graph automorphism|automorphism]] is a permutation of the [[Vertex (graph theory)|vertices]] such that edges are mapped to edges and non-edges are mapped to non-edges.<ref name=Godsil01/>  A graph is a '''vertex-transitive graph''' if, given any two vertices {{math|''v''{{sub|1}}}} and {{math|''v''{{sub|2}}}} of {{mvar|G}}, there is an automorphism {{math|''f''}} such that
:<math>f(v_1) = v_2.\ </math>

In other words, a graph is vertex-transitive if its [[automorphism group]] [[Group action (mathematics)|acts]] [[Group_action#Remarkable properties of actions|transitively]] on its vertices.<ref name=Godsil01>{{citation|first1=Chris|last1=Godsil|authorlink1=Chris Godsil|first2=Gordon|last2=Royle|authorlink2=Gordon Royle|title=Algebraic Graph Theory|series=[[Graduate Texts in Mathematics]]|volume=207|publisher=Springer |orig-year=2001 |isbn=978-1-4613-0163-9 |year=2013|url=https://books.google.com/books?id=GeSPBAAAQBAJ }}.</ref> A graph is vertex-transitive [[if and only if]] its [[graph complement]] is, since the group actions are identical.

Every [[symmetric graph]] without [[isolated vertex|isolated vertices]] is vertex-transitive, and every vertex-transitive graph is [[Regular graph|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]]).

== Finite examples ==
[[File:Tuncated tetrahedral graph.png|thumb|right|220px|The edges of the [[truncated tetrahedron]] form a vertex-transitive graph (also a [[Cayley graph]]) which is not [[symmetric graph|symmetric]].]]
Finite vertex-transitive graphs include the [[symmetric graph]]s (such as the [[Petersen graph]], the [[Heawood graph]] and the vertices and edges of the [[Platonic solid]]s).  The finite [[Cayley graph]]s (such as [[cube-connected cycles]]) are also vertex-transitive, as are the vertices and edges of the [[Archimedean solid]]s (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.<ref>{{citation|title=Cubic vertex-transitive graphs on up to 1280 vertices|author1=Potočnik P., Spiga P.  |author2=Verret G. |name-list-style=amp |journal=Journal of Symbolic Computation |volume = 50 | year = 2013|pages = 465–477|doi=10.1016/j.jsc.2012.09.002|arxiv=1201.5317|s2cid=26705221 }}.</ref>

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 graph]]s of [[edge-transitive graph|edge-transitive]] non-[[bipartite graph|bipartite]] graphs with [[parity (mathematics)|odd]] vertex degrees.<ref>{{citation
 | last1 = Lauri | first1 = Josef
 | last2 = Scapellato | first2 = Raffaele
 | isbn = 0-521-82151-7
 | mr = 1971819
 | page = 44
 | publisher = Cambridge University Press
 | series = London Mathematical Society Student Texts
 | title = Topics in graph automorphisms and reconstruction
 | url = https://books.google.com/books?id=hsymFm0E0uIC&pg=PA44
 | volume = 54
 | year = 2003}}. Lauri and Scapelleto credit this construction to Mark Watkins.</ref>

== Properties ==
The [[Connectivity (graph theory)|edge-connectivity]] of a connected vertex-transitive graph is equal to the [[regular graph|degree]] ''d'', while the [[Connectivity (graph theory)|vertex-connectivity]] will be at least 2(''d''&nbsp;+&thinsp;1)/3.<ref name=Godsil01/>
If the degree is 4 or less, or the graph is also [[edge-transitive graph|edge-transitive]], or the graph is a minimal [[Cayley graph]], then the vertex-connectivity will also be equal to ''d''.<ref>{{Citation|title=Technical Report TR-94-10|author=Babai, L.|year=1996|publisher=University of Chicago |url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |archive-url=https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |archive-date=2010-06-11 }}</ref>

== Infinite examples ==
Infinite vertex-transitive graphs include:
* infinite [[Path (graph theory)|paths]] (infinite in both directions)
* infinite [[Regular graph|regular]] [[tree (graph theory)|trees]], e.g. the [[Cayley graph]] of the [[free group]]
* graphs of [[Uniform tiling|uniform tessellations]] (see a [[List of uniform planar tilings|complete list]] of planar [[tessellation]]s), including all [[Tiling by regular polygons|tilings by regular polygons]]
* infinite [[Cayley graph]]s
* the [[Rado graph]]

Two [[countable]] vertex-transitive graphs are called [[Glossary of Riemannian and metric geometry#Q|quasi-isometric]] if the ratio of their [[distance function]]s 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 [[Reinhard Diestel|Diestel]] and [[Imre Leader|Leader]] in 2001.<ref>{{citation|first1=Reinhard|last1=Diestel|first2=Imre|last2=Leader|authorlink2=Imre Leader|url=http://www.math.uni-hamburg.de/home/diestel/papers/Cayley.pdf|title=A conjecture concerning a limit of non-Cayley graphs|journal=Journal of Algebraic Combinatorics|volume=14|issue=1|year=2001|pages=17–25|doi=10.1023/A:1011257718029|s2cid=10927964|doi-access=free}}.</ref>  In 2005, Eskin, Fisher, and Whyte confirmed the counterexample.<ref>{{cite arXiv|first1=Alex|last1=Eskin|first2=David|last2=Fisher|first3=Kevin|last3=Whyte|eprint=math.GR/0511647 |title=Quasi-isometries and rigidity of solvable groups|year=2005}}.</ref>

== See also ==
* [[Edge-transitive graph]]
* [[Lovász conjecture]]
* [[Semi-symmetric graph]]
* [[Zero-symmetric graph]]

== References ==
<references/>

== External links ==
* {{MathWorld | urlname=Vertex-TransitiveGraph | title=Vertex-transitive graph }}
* [https://staff.matapp.unimib.it/~spiga/census.html A census of small connected cubic vertex-transitive graphs]. Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.
* [https://zenodo.org/records/4010122 Vertex-transitive Graphs On Fewer Than 48 Vertices]. Gordon Royle and Derek Holt, 2020.

[[Category:Graph families]]
[[Category:Algebraic graph theory]]
[[Category:Regular graphs]]