Automorphisms of graphs

By Peter J. Cameron. 2003

71 citations recorded by the source corpus.

This chapter surveys automorphisms of finite graphs, concentrating on the asymmetry of typical graphs, prescribing automorphism groups (as either permutation groups or abstract groups), and special properties of vertex-transitive graphs and related classes. There are short digressions on infinite graphs and graph homomorphisms. 1 Graph automorphisms An automorphism of a graph G is a permutation g of the vertex set of G with the property that, for any vertices u and v, we have ug ∼ vg if and only if u ∼ v. (As usual, we use vg to denote the image of the vertex v under the permutation g. See [13] for the terminology and main results of permutation group theory.) This simple definition does not suffice for multigraphs; we need to specify a permutation of the edges as well as a permutation of the vertices, to ensure that the multiplicity of edges between two vertices is preserved. (Alternatively, a multigraph can be regarded as a weighted graph, where the weight au,v is the number of edges from u to v; an automorphism is required to satisfy aug,vg = au,v. This gives a slightly different description of automorphisms, but the action on the set of vertices is the same.) We will consider only simple graphs here.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/060f5293481ea32c320bba1f62653bb7b63fa5e3