Distance-transitive graph

	Email		Print
	Bookmark		Link

Distance-transitive graph

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 distance-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....
such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an 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....
of the graph that carries v to x and w to y.

A distance transitive graph is vertex transitive

Vertex-transitive graph

In mathematics, a vertex-transitive graph is a Graph G such that, given any two vertices v1 and v2 of G, there is some Graph automorphism...
and arc transitive

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...
as well as distance regular

Distance-regular graph

In mathematics, a distance-regular graph is a Regular graph Graph such that for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same....
.

A distance-transitive graph is interesting partly because it has a large automorphism group.

Discussion

Ask a question about 'Distance-transitive graph'

Start a new discussion about 'Distance-transitive graph'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In mathematics

Mathematics

Graph (mathematics)

Graph automorphism

Vertex-transitive graph

In mathematics, a vertex-transitive graph is a Graph G such that, given any two vertices v1 and v2 of G, there is some Graph automorphism...
and arc transitive

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...
as well as distance regular

Distance-regular graph

Finite group

In mathematics, a finite group is a group that has finite setly many elements. During the twentieth century, mathematicians investigated some aspects of the theory of finite groups in great depth: in particular, the local analysis of finite groups, and the theory of solvable groups and nilpotent groups....
s are the automorphism groups of distance-transitive graphs, especially of those whose diameter is 2.

Distance-transitive graphs were first defined in 1971 by Norman Biggs and D. H. Smith, who showed that there are only 12 finite trivalent

Cubic graph

In the mathematics field of graph theory, a cubic graph is a graph where all vertex are incident to exactly three edge . In other words a cubic graph is a 3-regular graph....
distance-transitive graphs. These are:

Graph Name	Vertex Count	Diameter Diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints are on the circle....	Girth
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 .... K₄	4	1	3
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.... K_3,3	6	2	4
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....	10	2	5
Graph of the cube Cube A cube is a three-dimensional space solid object bounded by six square faces, facets or sides, with three meeting at each wikt:vertex. The cube can also be called a Regular polyhedron hexahedron and is one of the five Platonic solids....	8	3	4
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....	14	3	6
Pappus graph Pappus graph In the mathematics field of graph theory, the Pappus graph is a 3-regular graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration....	18	4	6
Coxeter graph	28	4	7
Tutte–Coxeter graph	30	4	8
Graph of the dodecahedron Dodecahedron A dodecahedron is any polyhedron with twelve faces, but usually a regular dodecahedron is meant: a Platonic solid composed of twelve regular pentagonal faces, with three meeting at each vertex....	20	5	5
Desargues graph Desargues graph In the mathematics field of graph theory, the Desargues graph is a Distance-transitive graph cubic graph with 20 vertices and 30 edges. It arises from several different combinatorial constructions, has a high level of symmetry, is the only known planar graph cubic partial cube, and has been applied in chemical databases....	20	5	6
Biggs–Smith graph.	102	7	9
Foster graph Foster graph In graph theory the Foster graph is a graph on 90 vertices and 135 arcs. It is the unique Distance-transitive graph graph with intersection array ....	90	8	10

Independently in 1969 a Russian group led by Georgy Adelson-Velsky

Georgy Adelson-Velsky

Georgy Maximovich Adelson-Velsky , is a Russian mathematician and computer scientist. Along with Yevgeniy Landis, he invented the AVL tree in 1962....
showed that there exist graphs that are distance-regular but not distance-transitive. The only graph of this type with degree three is the 126-vertex Tutte 12-cage. Complete lists of distance-transitive graphs are known for some degrees larger than three, but the classification of distance-transitive graphs with arbitrarily large vertex degree remains open.

Square rook's graph

Rook's graph

In graph theory, a rook's graph is a graph that represents all legal moves of the Rook chess Chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move....
s provide examples of distance-transitive graphs of arbitrarily high degree.

Distance-transitive graph

External links