An identity graph, sometimes also known as an asymmetric graph or rigid graph (Albertson and Collins 1996), is a graph possessing a single graph automorphism.
The numbers of connected identity graphs on , 2, ... nodes are 1, 0, 0, 0, 0, 8, 144, 3552, 131452, ... (OEIS A124059), with the eight identity graphs of order six (all of which are connected) illustrated above.
The numbers of identity graphs on , 2, ... nodes are given by 1, 0, 0, 0, 0, 8, 152, 3696, 135004, ... (OEIS A003400), with the eight 7-node disconnected identity graphs illustrated above.
The following table summarizes some named identity graphs, illustrated above.
graph | |
1 | singleton graph |
7 | self-dual graph 2 |
12 | Frucht graph |
20 | (10,3)-configuration 4 Levi graph, 20-snarks 2 and 3 |
23 | Kittell graph |
25 | 25-Paulus graphs 2 and 4 |
26 | 26-Paulus graph 10 |
50 | 50-cubic nonhamiltonian graphs 1 and 2 |
52 | 52-cubic nonhamiltonian graph 1 |
58 | (3,9)-cage graph 7, 9, 11, and 13 |
222 | Gardner graph |
Integral identity graphs are apparently rather rare, with four examples being the singleton graph and -, -, and -Paulus graphs.