Graph Families Defined By Their Automorphisms
Several families of graphs are defined by having certain types of automorphisms:
- An asymmetric graph is an undirected graph without any nontrivial automorphisms.
- A vertex-transitive graph is an undirected graph in which every vertex may be mapped by an automorphism into any other vertex.
- An edge-transitive graph is an undirected graph in which every edge may be mapped by an automorphism into any other edge.
- A symmetric graph is a graph such that every pair of adjacent vertices may be mapped by an automorphism into any other pair of adjacent vertices.
- A distance-transitive graph is a graph such that every pair of vertices may be mapped by an automorphism into any other pair of vertices that are the same distance apart.
- A semi-symmetric graph is a graph that is edge-transitive but not vertex-transitive.
- A half-transitive graph is a graph that is vertex-transitive and edge-transitive but not symmetric.
- A skew-symmetric graph is a directed graph together with a permutation σ on the vertices that maps edges to edges but reverses the direction of each edge. Additionally, σ is required to be an involution.
Inclusion relationships between these families are indicated by the following table:
| distance-transitive | distance-regular | strongly regular | ||
| symmetric (arc-transitive) | t-transitive, t ≥ 2 | |||
| (if connected) | ||||
| vertex- and edge-transitive | edge-transitive and regular | edge-transitive | ||
| vertex-transitive | regular | |||
| Cayley graph |
Read more about this topic: Graph Automorphism
Famous quotes containing the words graph, families and/or defined:
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)
“We as a nation need to be reeducated about the necessary and sufficient conditions for making human beings human. We need to be reeducated not as parents—but as workers, neighbors, and friends; and as members of the organizations, committees, boards—and, especially, the informal networks that control our social institutions and thereby determine the conditions of life for our families and their children.”
—Urie Bronfenbrenner (b. 1917)
“Coming to terms with the rhythms of women’s lives means coming to terms with life itself, accepting the imperatives of the body rather than the imperatives of an artificial, man-made, perhaps transcendentally beautiful civilization. Emphasis on the male work-rhythm is an emphasis on infinite possibilities; emphasis on the female rhythms is an emphasis on a defined pattern, on limitation.”
—Margaret Mead (1901–1978)