Asymmetric graph

The eight 6-vertex asymmetric graphs

The Frucht graph, the smallest asymmetric cubic graph.

Graph families defined by their automorphisms
distance-transitive	${\boldsymbol {\rightarrow }}$	distance-regular	${\boldsymbol {\leftarrow }}$	strongly regular
${\boldsymbol {\downarrow }}$
symmetric (arc-transitive)	${\boldsymbol {\leftarrow }}$	t-transitive, t ≥ 2		skew-symmetric
${\boldsymbol {\downarrow }}$
_{(if connected)} vertex- and edge-transitive	${\boldsymbol {\rightarrow }}$	edge-transitive and regular	${\boldsymbol {\rightarrow }}$	edge-transitive
${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$
vertex-transitive	${\boldsymbol {\rightarrow }}$	regular	${\boldsymbol {\rightarrow }}$	_{(if bipartite)} biregular
${\boldsymbol {\uparrow }}$
Cayley graph	${\boldsymbol {\leftarrow }}$	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 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 regular graphs have ten vertices; there exist ten-vertex asymmetric graphs that are 4-regular and 5-regular.^[2]^[3] One of the two smallest asymmetric cubic graphs is the twelve-vertex Frucht graph discovered in 1939.^[4] 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". In contrast, again informally, "almost all infinite graphs are symmetric." More specifically, countable infinite random graphs in the Erdős–Rényi model are, with probability 1, isomorphic to the highly symmetric Rado graph.^[1]

Trees

The smallest asymmetric tree has seven vertices: it consists of three paths of lengths 1, 2, and 3, linked at a common endpoint.^[5] 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

1 2 3 4 5 Erdős, P.; Rényi, A. (1963), "Asymmetric graphs" (PDF), Acta Mathematica Hungarica, 14 (3): 295–315, doi:10.1007/BF01895716 .
↑ Baron, G.; Imrich, W. (1969), "Asymmetrische reguläre Graphen", Acta Mathematica Academiae Scientiarum Hungaricae, 20: 135–142, doi:10.1007/BF01894574, MR 0238726 .
↑ Gewirtz, Allan; Hill, Anthony; Quintas, Louis V. (1969), "The minimal number of points for regular asymmetric graphs", Universidad Técnica Federico Santa Maria. Scientia, 138: 103–111, MR 0266818 .
↑ Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804 .
↑ Quintas, Louis V. (1967), "Extrema concerning asymmetric graphs", Journal of Combinatorial Theory, 3 (1): 57–82, doi:10.1016/S0021-9800(67)80018-8 .

Wikimedia Commons has media related to Asymmetric graphs.

This article is issued from Wikipedia - version of the 6/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.