Asymmetric graph
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 onto itself 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.
Examples
The smallest asymmetric non-trivial graphs have 6 vertices.[1] The smallest asymmetric cubic graph is the Frucht graph discovered in 1939.[2][3] 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]
Random graphs
The proportion of graphs on n vertices with nontrivial automorphism tends to zero as n grows, which is informally expressed as "almost all finite graphs are asymmetric".[4] In contrast, again informally, "almost all infinite graphs are symmetric".[1] More specifically, countable infinite random graphs in the Erdős–Rényi model are, with probability 1, isomorphic to the highly symmetric Rado graph.
Trees
The smallest asymmetric tree has seven vertices: it consists of three paths of lengths 1, 2, and 3, linked at a common endpoint. In contrast to the situation for graphs, almost all trees are symmetric. In particular, if a tree is chosen uniformly at random among all trees on n labeled nodes, then with probability tending to 1 as n increases, the tree will contain some two leaves adjacent to the same node and will have symmetries exchanging these two leaves.[1]
References
- ^ a b c d e Erdős, P.; Rényi, A. (1963), "Asymmetric graphs" (PDF), Acta Mathematica Hungarica, 14 (3): 295–315, doi:10.1007/BF01895716.
- ^ Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.
- ^ Skiena, S. (1990), Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Reading, MA: Addison-Wesley.
- ^ Godsil, Christopher David; Royle, Gordon (2001), Algebraic Graph Theory, ISBN 0387952209.