In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a vertex-transitive graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...

in which, given any two vertices and of , there is some

automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphis ...

f : G \to G\

such that :

f(v_1) = v_2.\

In other words, a graph is vertex-transitive if its

automorphism group In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...

acts The Acts of the Apostles ( grc-koi, Πράξεις Ἀποστόλων, ''Práxeis Apostólōn''; la, Actūs Apostolōrum) is the fifth book of the New Testament; it tells of the founding of the Christian Church and the spread of its message ...

transitively on its vertices.. A graph is vertex-transitive

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicond ...

its graph complement is, since the group actions are identical. Every

symmetric graph In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In oth ...

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 In geometry, the truncated tetrahedron is an Archimedean solid. It has 4 regular hexagonal faces, 4 equilateral triangle faces, 12 vertices and 18 edges (of two types). It can be constructed by truncating all 4 vertices of a regular tetrahedr ...

), and not all regular graphs are vertex-transitive (for example, the

Frucht graph In the mathematical field of graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939. The Frucht graph is a pancyclic, Halin graph with chromati ...

and Tietze's graph).

Finite examples

Finite vertex-transitive graphs include the

s (such as the

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 ...

, the

Heawood graph Heawood is a surname. Notable people with the surname include: *Jonathan Heawood, British journalist *Percy John Heawood (1861–1955), British mathematician **Heawood conjecture **Heawood graph Heawood is a surname. Notable people with the surname ...

and the vertices and edges of the

Platonic solid In geometry, a Platonic solid is a convex, regular polyhedron in three-dimensional Euclidean space. Being a regular polyhedron means that the faces are congruent (identical in shape and size) regular polygons (all angles congruent and all edge ...

s). The finite

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayl ...

s (such as

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 The cube-connected ...

) are also vertex-transitive, as are the vertices and edges of the

Archimedean solid In geometry, an Archimedean solid is one of the 13 solids first enumerated by Archimedes. They are the convex uniform polyhedra composed of regular polygons meeting in identical vertices, excluding the five Platonic solids (which are composed o ...

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. 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 In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

s of

edge-transitive In geometry, a polytope (for example, a polygon or a polyhedron) or a tiling is isotoxal () or edge-transitive if its symmetries act transitively on its edges. Informally, this means that there is only one type of edge to the object: given two ...

non- bipartite graphs with odd vertex degrees.

Properties

The

edge-connectivity In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed. The edge-connectivity of a graph is the largest for which the graph is -edge-connected. Edge connectivity and the enumeratio ...

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

, or the graph is a minimal

, then the vertex-connectivity will also be equal to ''d''.

Infinite examples

Infinite vertex-transitive graphs include: * infinite paths (infinite in both directions) * infinite regular

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...

, e.g. the

of the

free group In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1 ...

* graphs of uniform tessellations (see a complete list of planar

tessellation A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of ...

s), including all tilings by regular polygons * infinite

s * the

Rado graph In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whet ...

Two

countable In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...

vertex-transitive graphs are called quasi-isometric if the ratio of their

distance function In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general sett ...

s is bounded from below and from above. A well known

conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 1 ...

stated that every infinite vertex-transitive graph is quasi-isometric to a

. A counterexample was proposed by Diestel and

Leader Leadership, both as a research area and as a practical skill, encompasses the ability of an individual, group or organization to "lead", influence or guide other individuals, teams, or entire organizations. The word "leadership" often gets view ...

in 2001. In 2005, Eskin, Fisher, and Whyte confirmed the counterexample..

References

External links

* {{MathWorld , urlname=Vertex-TransitiveGraph , title=Vertex-transitive graph
A census of small connected cubic vertex-transitive graphs
Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012. Graph families Algebraic graph theory Regular graphs

Finite examples

Properties

Infinite examples

See also

References

External links