Edge-transitive graph
Encyclopedia
In the mathematical
field of graph theory
, an edge-transitive graph is a graph
G such that, given any two edges e1 and e2 of G, there is an
automorphism
of G that maps e1 to e2.
In other words, a graph is edge-transitive if its automorphism group acts transitively
upon its edges.
Edge-transitive graphs include any complete bipartite graph
, and any symmetric graph
, such as the vertices and edges of the cube
. Symmetric graphs are also vertex-transitive
(if they are connected), but in general edge-transitive graphs need not be vertex-transitive. The Gray graph
is an example of a graph which is edge-transitive but not vertex-transitive. All such graphs are bipartite
, and hence can be colored
with only two colors.
An edge-transitive graph that is also regular
, but not vertex-transitive, is called semi-symmetric
. The Gray graph
again provides an example.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, an edge-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 edges e1 and e2 of G, there is an
automorphism
Graph automorphism
In the mathematical field of 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 G that maps e1 to e2.
In other words, a graph is edge-transitive if its automorphism group acts transitively
Group action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. 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 transformations of the set...
upon its edges.
Examples and properties
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.- Definition :...
, and any symmetric graphSymmetric graph
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...
, such as the vertices and edges of the cube
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. The cube can also be called a regular hexahedron and is one of the five Platonic solids. It is a special kind of square prism, of rectangular parallelepiped and...
. Symmetric graphs are also vertex-transitive
Vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...
(if they are connected), but in general edge-transitive graphs need not be vertex-transitive. The Gray graph
Gray graph
In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 , then discovered independently by Bouwer 1968 in reply to a question...
is an example of a graph which is edge-transitive but not vertex-transitive. All such graphs are bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
, and hence can be colored
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
with only two colors.
An edge-transitive graph that is also 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. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
, but not vertex-transitive, is called semi-symmetric
Semi-symmetric graph
In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive....
. The Gray graph
Gray graph
In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 , then discovered independently by Bouwer 1968 in reply to a question...
again provides an example.