Graph Automorphism

Graph Automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

Formally, an automorphism of a graph G = (V,E) is a permutation σ of the vertex set V, such that the pair of vertices (u,v) form an edge if and only if the pair (σ(u),σ(v)) also form an edge. That is, it is a graph isomorphism from G to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs. The composition of two automorphisms is another automorphism, and the set of automorphisms of a given graph, under the composition operation, forms a group, the automorphism group of the graph. In the opposite direction, by Frucht's theorem, all groups can be represented as the automorphism group of a connected graph – indeed, of a cubic graph.

Read more about Graph Automorphism:  Computational Complexity, Algorithms, Software and Applications, Symmetry Display, Graph Families Defined By Their Automorphisms

Other articles related to "graph automorphism, graphs, automorphisms, graph, automorphism":

Graph Automorphism - Graph Families Defined By Their Automorphisms
... Several families of graphs are defined by having certain types of automorphisms An asymmetric graph is an undirected graph without any nontrivial automorphisms ... A vertex-transitive graph is an undirected graph in which every vertex may be mapped by an automorphism into any other vertex ... An edge-transitive graph is an undirected graph in which every edge may be mapped by an automorphism into any other edge ...

Famous quotes containing the word graph:

    When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.
    Marshall McLuhan (1911–1980)