All Topics  
Vertex-transitive graph

 

 
   Email Print
   Bookmark   Link
 

 

Vertex-transitive graph
 
 
  Topics Vertex-transitive graph Topic Home

In mathematics
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
, 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 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....


f : V(G) ? V(G)


such that

f (v1) = v2.


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 symmetry of objects using group . 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 transformation of the set....
 upon its vertices.






Discussion
Ask a question about 'Vertex-transitive graph'
Start a new discussion about 'Vertex-transitive graph'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In mathematics
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
, 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 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....


f : V(G) ? V(G)


such that

f (v1) = v2.


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 symmetry of objects using group . 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 transformation of the set....
 upon its vertices. A graph is vertex-transitive if and only if
If and only if

If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements....
 its graph complement is, since the group actions are identical.

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....
. Every arc-transitive graph
Arc-transitive graph

In mathematics, an arc-transitive graph is a graph G such that, given any two edges e1 = u1v1 and e2 = u2v2 of G, there are two Graph automorphisms...
 without isolated vertices is also vertex-transitive.

Finite examples

  • Heawood graph
    Heawood graph

    In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges. The graph is cubic graph, and all cycles in the graph have six or more edges....
  • Kneser graph
    Kneser graph

    In graph theory, the Kneser graph is the graph whose vertices correspond to the -element subsets of a set of elements, and where two vertices are connected if and only if the two corresponding sets are disjoint....
     and its complement Johnson graph
    • Petersen graph
      Petersen graph

      In 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....
  • finite Cayley graph
    Cayley graph

    In mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph theory that encodes the structure of a discrete group....
    s
    • circulant graphs
      • Complete graph
        Complete graph

        In graph theory, a complete graph is a simple graph in which every pair of distinct vertex is connected by an edge . The complete graph on n vertices has n vertices and n/2 edges, and is denoted by ....
      • Cycle graph
        Cycle graph

        In graph theory, a cycle graph is a graph that consists of a single path , or in other words, some number of vertices connected in a closed chain....
      • Complete bipartite graph
        Complete bipartite graph

        In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set....
         
  • graphs of Platonic solid
    Platonic solid

    In geometry, a Platonic solid is a convex set polyhedron that is regular polyhedron, in the sense of a regular polygon. Specifically, the faces of a Platonic solid are congruence regular polygons, with the same number of faces meeting at each vertex....
    s and Archimedean solid
    Archimedean solid

    In geometry an Archimedean solid is a highly symmetric, semi-regular convex set polyhedron composed of two or more types of regular polygons meeting in identical vertex ....
    s


Infinite examples

  • infinite path
    Path (graph theory)

    In graph theory, a path in a graph is a sequence of vertex such that from each of its vertices there is an edge to the next vertex in the sequence....
     (infinite in both directions)
  • infinite 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....
     tree
    Tree (graph theory)

    In mathematics, more specifically graph theory, a tree is a graph in which any two Vertex are connected by exactly one path . Alternatively, any connectedness graph with no Cycle is a tree....
    , e.g. the Cayley graph
    Cayley graph

    In mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph theory that encodes the structure of a discrete group....
     of the free group
    Free group

    In 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 tessellation
    Uniform tessellation

    In mathematics, a uniform tessellation is a tessellation of a d-dimensional space, or a surface, such that all its Vertex-transitive, i.e., there is the same combination and arrangement of faces at each vertex....
    s (see a complete list
    List of uniform planar tilings

    This table shows the 11 convex Uniform tessellations of the Euclidean geometry, and their dual tilings.There are three regular, and eight semiregular, Tiling by regular polygons in the plane....
     of planar tessellation
    Tessellation

    A tessellation or tiling of the plane is a collection of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of the parts of the plane or of other surfaces....
    s), including all tilings by regular polygons
    Tiling by regular polygons

    Plane Tessellation by regular polygons have been widely used since antiquity. The first systematic mathematical treatment was that of Johannes Kepler in Harmonices Mundi....
  • infinite Cayley graph
    Cayley graph

    In mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph theory that encodes the structure of a discrete group....
    s
  • the Rado graph
    Rado graph

    File:Rado graph.svgIn graph theory, the Rado graph, also known as the random 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 embedding of G into R....


Infinite vertex-transitive graphs

Two countable vertex-transitive graphs are called quasi-isometric
Glossary of Riemannian and metric geometry

This is a glossary of some terms used in Riemannian geometry and metric geometry — it doesn't cover the terminology of differential topology. The following articles may also be useful....
 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, the Cayley graph, also known as the Cayley colour graph, is the graph theory that encodes the structure of a discrete 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.Educated at St Paul's School and Trinity College, Cambridge, he was also a member of the British team in the International Mathematical Olympiad in 1981: he later led the team in 1999, 2000 and 2001....
. Most recently, Eskin, Fisher, and Whyte confirmed the counterexample.

See also

  • Edge-transitive graph
    Edge-transitive graph

    In mathematics, an edge-transitive graph is a Graph G such that, given any two edges e1 and e2 of G, there is an...
  • Lovász conjecture
    Lovász conjecture

    In graph theory, the Lov?sz conjecture is a classical problem on Hamiltonian paths in graphs. It says:The original article of Lov?sz stated the result in the opposite, but...
  • Semi-symmetric graph
    Semi-symmetric graph

    In mathematics, a semi-symmetric graph is an undirected graph that is edge-transitive graph and regular graph, but not Vertex-transitive graph....