Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelled k-regular simple graph on n vertices has only the trivial group of automorphisms is asymptotic to 1 as n → ∞ with 3≦k=O(n ^1/2-c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelled k-regular simple graphs on n vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs.