Asymmetric graph
From Wikipedia, the free encyclopedia
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.
The smallest asymmetric non-trivial graphs have 6 vertices.[1] The smallest asymmetric regular graphs have ten vertices; there exist 10-vertex asymmetric graphs that are 4-regular and 5-regular.[2][3] One of the five smallest asymmetric cubic graphs[4] is the twelve-vertex Frucht graph discovered in 1939.[5] According to a strengthened version of Frucht's theorem, there are infinitely many asymmetric cubic graphs.
Properties
The class of asymmetric graphs is closed under complements: a graph G is asymmetric if and only if its complement is.[1] Any n-vertex asymmetric graph can be made symmetric by adding and removing a total of at most n/2 + o(n) edges.[1]
