Surf Wiki
Save to docs
general/graph-families

From Surf Wiki (app.surf) — the open knowledge base

Asymmetric graph

Undirected graph with no non-trivial symmetries

Asymmetric graph
Summary

Undirected graph with no non-trivial symmetries

The eight 6-vertex asymmetric graphs
cubic graphs]].

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.

Examples

The smallest asymmetric non-trivial graphs have 6 vertices. The smallest asymmetric regular graphs have ten vertices; there exist 10-vertex asymmetric graphs that are 4-regular and 5-regular.{{citation

Properties

The class of asymmetric graphs is closed under complements: a graph G is asymmetric if and only if its complement is. Any n-vertex asymmetric graph can be made symmetric by adding and removing a total of at most n/2 + o(n) edges.

Random graphs

The proportion of graphs on n vertices with a 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 have nontrivial symmetries." More specifically, countably 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.

References

References

  1. (1976). "Computer investigation of cubic graphs". Dept. of Mathematics and Computing Science, Eindhoven University of Technology.
  2. (1939). "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.". Compositio Mathematica.
  3. (1963). "Asymmetric graphs". [[Acta Mathematica Hungarica]].
  4. Quintas, Louis V.. (1967). "Extrema concerning asymmetric graphs". [[Journal of Combinatorial Theory]].
Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

graph-families asymmetry
Want to explore this topic further?

Ask Mako anything about Asymmetric graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report