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:
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)
“The authoritarian child-rearing style so often found in working-class families stems in part from the fact that parents see around them so many young people whose lives are touched by the pain and delinquency that so often accompanies a life of poverty. Therefore, these parents live in fear for their children’s future—fear that they’ll lose control, that the children will wind up on the streets or, worse yet, in jail.”
—Lillian Breslow Rubin (20th century)
“The cliché that women, more consistently than men, turn inward for sustenance seems to mean, in practice, that women have richly defined the ways in which imagination creates possibility; possibility that society denies.”
—Patricia Meyer Spacks (b. 1929)