Vertex-transitive graph

In mathematics, a vertex-transitive graph is a graph "G" such that, given any two vertices v₁ and v₂ of "G", there is some automorphism

:"f" : "V(G)" → "V(G)"

such that

:"f" (v₁) = v₂.

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 vertex-transitive graph is regular. Every arc-transitive graph without isolated vertices is also vertex-transitive.

Finite examples

* Heawood graph
* Kneser graph and its complement Johnson graph
** Petersen graph
* finite Cayley graphs
** circulant graphs
*** Complete graph
*** Cycle graph
*** Complete bipartite graph $K_{n,n}$
* graphs of Platonic solids and Archimedean solids

Infinite examples

* infinite path (infinite in both directions)
* infinite regular tree, e.g. the Cayley graph of the free group
* graphs of uniform tessellations (see a complete list of planar tessellations), including all tilings by regular polygons
* infinite Cayley graphs

Infinite vertex-transitive graphs

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.

See also

* Edge-transitive graph
* Lovász conjecture
* Semi-symmetric graph

References

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

Edge-transitive graph — In mathematics, an edge transitive graph is a graph G such that, given any two edges e 1 and e 2 of G , there is an automorphism of G that maps e 1 to e 2.In other words, a graph is edge transitive if its automorphism group acts transitively upon … Wikipedia
Distance-transitive graph — The Biggs Smith graph, the largest 3 regular distance transitive graph. Graph families defined by their automorphisms distance transitive … Wikipedia
Graph automorphism — In graph theoretical mathematics, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge vertex connectivity.Formally, an automorphism of a graph G = ( V , E ) is a permutation sigma;… … Wikipedia
Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges … Wikipedia
Vertex (graph theory) — For other uses, see Vertex (disambiguation). A graph with 6 vertices and 7 edges where the vertex number 6 on the far left is a leaf vertex or a pendant vertex In graph theory, a vertex (plural vertices) or node is the fundamental unit out of… … Wikipedia
Petersen graph — Infobox graph name = Petersen graph image caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes. namesake = Julius Petersen vertices = 10 edges = 15 radius = 2 diameter = 2 girth = 5 chromatic … Wikipedia
Cayley graph — In mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph that encodes the structure of a discrete group. Its definition is suggested by Cayley s theorem (named after Arthur Cayley) and uses a particular, usually… … Wikipedia
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 (nodes or edges) which need to be removed to disconnect the remaining nodes from each other[1]. It is… … Wikipedia
Coxeter graph — This article is about the 3 regular graph. For the graph associated with a Coxeter group, see Coxeter diagram. Coxeter graph The Coxeter graph Vertices 28 Edges 42 … Wikipedia
List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 … Wikipedia

Academic Dictionaries and Encyclopedias

Vertex-transitive graph

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Vertex-transitive graph

Look at other dictionaries:

Share the article and excerpts

Direct link