In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, 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 discret ...
such that, given any two edges and of , there is an
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 automorphism ...
of that
maps
A map is a symbolic depiction of interrelationships, commonly spatial, between things within a space. A map may be annotated with text and graphics. Like any graphic, a map may be fixed to paper or other durable media, or may be displayed on ...
to .
In other words, a graph is edge-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
transitively 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 graphs, such as the vertices and edges of the
cube
A cube or regular hexahedron is a three-dimensional space, three-dimensional solid object in geometry, which is bounded by six congruent square (geometry), square faces, a type of polyhedron. It has twelve congruent edges and eight vertices. It i ...
.
Symmetric graphs are also
vertex-transitive (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,
(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.
Dictionary definitions
The word ''colored'' wa ...
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, 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