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 ...
, an edge-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 discre ...
such that, given any two edges and of , there is an
automorphism of that
maps to .
In other words, a graph is edge-transitive if its
automorphism group acts
transitively
Transitivity or transitive may refer to:
Grammar
* Transitivity (grammar), a property of verbs that relates to whether a verb can take direct objects
* Transitive verb, a verb which takes an object
* Transitive case, a grammatical case to mark a ...
on its edges.
Examples and properties
The number of connected simple edge-transitive graphs on n vertices is 1, 1, 2, 3, 4, 6, 5, 8, 9, 13, 7, 19, 10, 16, 25, 26, 12, 28 ...
Edge-transitive graphs include all
symmetric graph, such as the vertices and edges of the
cube
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross.
The cube is the on ...
.
Symmetric graphs are also
vertex-transitive
In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of fa ...
(if they are
connected), but in general edge-transitive graphs need not be vertex-transitive. Every
connected edge-transitive graph that is not vertex-transitive must be
bipartite
Bipartite may refer to:
* 2 (number)
* Bipartite (theology), a philosophical term describing the human duality of body and soul
* Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...
,
(and hence can be
colored
''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow Era to refer to an African American. In many places, it may be considered a slur, though it has taken on a special meaning in South ...
with only two colors), and either semi-symmetric or
biregular.
[.]
Examples of edge but not vertex transitive graphs include the
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..Electronic edition page 17.
Graph theory ...
s
where m ≠ n, which includes the star graphs
. For graphs on n vertices, there are (n-1)/2 such graphs for odd n and (n-2) for even n.
Additional edge transitive graphs which are not symmetric can be formed as subgraphs of these complete bi-partite graphs in certain cases. Subgraphs of complete bipartite graphs K
m,n exist when m and n share a factor greater than 2. When the greatest common factor is 2, subgraphs exist when 2n/m is even or if m=4 and n is an odd multiple of 6. So edge transitive subgraphs exist for K
3,6, K
4,6 and K
5,10 but not K
4,10. An alternative construction for some edge transitive graphs is to add vertices to the midpoints of edges of a symmetric graph with v vertices and e edges, creating a bipartite graph with e vertices of order 2, and v of order 2e/v.
An edge-transitive graph that is also
regular
The term regular can mean normal or in accordance with rules. It may refer to:
People
* Moses Regular (born 1971), America football player
Arts, entertainment, and media Music
* "Regular" (Badfinger song)
* Regular tunings of stringed instrum ...
, but still not vertex-transitive, is called
semi-symmetric. The
Gray graph, a cubic graph on 54 vertices, is an example of a regular graph which is edge-transitive but not vertex-transitive. The
Folkman graph, a quartic graph on 20 vertices is the smallest such graph.
The
vertex connectivity of an edge-transitive graph always equals its
minimum degree.
See also
*
Edge-transitive (in geometry)
References
External links
* {{MathWorld , urlname=Edge-TransitiveGraph , title=Edge-transitive graph
Graph families
Algebraic graph theory