Vertex-transitive graph
Encyclopedia
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
such that
In other words, a graph is vertex-transitive if its automorphism group acts transitively
upon its vertices. 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
).
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).
of a vertex-transitive graph is equal to the degree
d, while the vertex-connectivity
will be at least 2(d+1)/3.
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.
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 states that every infinite vertex-transitive graph is quasi-isometric to a Cayley graph
. A counterexample has been proposed by Diestel and Leader
. Most recently, Eskin, Fisher, and Whyte confirmed the counterexample.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a vertex-transitive graph is a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
G such that, given any two vertices v1 and v2 of G, there is some automorphism
Graph automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....
such that
In other words, a graph is vertex-transitive if its automorphism group acts transitively
Group action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
upon its vertices. A graph is vertex-transitive if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
its graph complement is, since the group actions are identical.
Every symmetric graph
Symmetric graph
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...
without isolated vertices is vertex-transitive, and every vertex-transitive graph is regular
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
. However, not all vertex-transitive graphs are symmetric (for example, the edges of the truncated tetrahedron
Truncated tetrahedron
In geometry, the truncated tetrahedron is an Archimedean solid. It has 4 regular hexagonal faces, 4 regular triangular faces, 12 vertices and 18 edges.- Area and volume :...
), and not all regular graphs are vertex-transitive (for example, the Frucht graph
Frucht graph
In the mathematical field of graph theory, the Frucht graph is a 3-regular graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939....
).
Finite examples
Symmetric graph
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...
s (such as the Petersen graph
Petersen graph
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...
, the Heawood graph
Heawood graph
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.-Combinatorial properties:...
and the vertices and edges of the Platonic solid
Platonic solid
In geometry, a Platonic solid is a convex polyhedron that is regular, in the sense of a regular polygon. Specifically, the faces of a Platonic solid are congruent regular polygons, with the same number of faces meeting at each vertex; thus, all its edges are congruent, as are its vertices and...
s). The finite Cayley graph
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
s (such as cube-connected cycles
Cube-connected cycles
In graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by for use as a network topology in parallel computing.- Definition :...
) are also vertex-transitive, as are the vertices and edges of the Archimedean solid
Archimedean solid
In geometry an Archimedean solid is a highly symmetric, semi-regular convex polyhedron composed of two or more types of regular polygons meeting in identical vertices...
s (though only two of these are symmetric).
Properties
The edge-connectivityConnectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
of a vertex-transitive graph is equal to the degree
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
d, while the vertex-connectivity
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
will be at least 2(d+1)/3.
If the degree is 4 or less, or the graph is also edge-transitive
Edge-transitive graph
In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is anautomorphism of G that maps e1 to e2....
, or the graph is a minimal Cayley graph
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
, then the vertex-connectivity will also be equal to d.
Infinite examples
Infinite vertex-transitive graphs include:- infinite pathsPath (graph theory)In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
(infinite in both directions) - infinite regularRegular graphIn graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
treesTree (graph theory)In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
, e.g. the Cayley graphCayley graphIn mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
of the free groupFree groupIn mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses... - graphs of uniform tessellationUniform tessellationIn geometry, a uniform tessellation is a vertex-transitive tessellations made from uniform polytope facets. All of its vertices are identical and there is the same combination and arrangement of faces at each vertex....
s (see a complete list of planar tessellationTessellationA tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
s), including all tilings by regular polygonsTiling by regular polygonsPlane tilings by regular polygons have been widely used since antiquity. The first systematic mathematical treatment was that of Kepler in Harmonices Mundi.- Regular tilings :... - infinite Cayley graphCayley graphIn mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
s - the Rado graphRado graphIn the mathematical field of graph theory, the Rado graph, also known as the random graph or the Erdős–Renyi graph, is the unique countable graph R such that for any finite graph G and any vertex v of G, any embedding of G − v as an induced subgraph of R can be extended to an...
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 states that every infinite vertex-transitive graph is quasi-isometric to a Cayley graph
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
. A counterexample has been proposed by Diestel and Leader
Imre Leader
Imre Bennett Leader is a British mathematician and Professor of Pure Mathematics, specifically combinatorics, at the University of Cambridge....
. Most recently, Eskin, Fisher, and Whyte confirmed the counterexample.