Asymmetric graph

Graph families defined by their automorphisms
distance-transitive → distance-regular ← strongly regular
↓
symmetric (arc-transitive) ← t-transitive, t ≥ 2 skew-symmetric
↓
(if connected)
vertex- and edge-transitive 		→ edge-transitive and regular → edge-transitive
↓ ↓ ↓
vertex-transitive → regular → (if bipartite)
biregular
↑
Cayley graph ← zero-symmetric asymmetric

In graph theory, a branch of mathematics, an undirected graph is called an asymmetric graph if it has no nontrivial symmetries.

Formally, an automorphism of a graph is a permutation p of its vertices with the property that any two vertices u and v are adjacent if and only if p(u) and p(v) are adjacent. The identity mapping of a graph is always an automorphism, and is called the trivial automorphism of the graph. An asymmetric graph is a graph for which there are no other automorphisms.

Note that the term "asymmetric graph" is not a negation of the term "symmetric graph," as the latter refers to a stronger condition than possessing nontrivial symmetries.

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.