Identity Graph

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 n=1, 2, ... nodes are 1, 0, 0, 0, 0, 8, 144, 3552, 131452, ... (OEIS A124059), with the the eight identity graphs of order six (all of which are connected) illustrated above.


The numbers of identity graphs on n=1, 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.

|V(G)|graph G
1singleton graph
7self-dual graph 2
12Frucht graph
20(10,3)-configuration 4 Levi graph, 20-snarks 2 and 3
23Kittell graph
2525-Paulus graphs 2 and 4
2626-Paulus graph 10
5050-cubic nonhamiltonian graphs 1 and 2
5252-cubic nonhamiltonian graph 1
58(3,9)-cage graph 7, 9, 11, and 13
222Gardner graph

Integral identity graphs are apparently rather rare, with four examples being the singleton graph K_1 and (25,2)-, (25,4)-, and (26,10)-Paulus graphs.

See also

Automorphism Group, Graph Automorphism, Rigid Graph, Symmetric Graph

Explore with Wolfram|Alpha


Albertson, M. and Collins, K. "Symmetry Breaking in Graphs." Electronic J. Combinatorics 3, No. 1, R18, 17 pp., 1996., F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 220, 1973.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, pp. 24-25, 1993.Sloane, N. J. A. Sequences A003400/M4575 and A124059 in "The On-Line Encyclopedia of Integer Sequences."Steinbach, P. Field Guide to Simple Graphs. Albuquerque, NM: Design Lab, 1990.

Referenced on Wolfram|Alpha

Identity Graph

Cite this as:

Weisstein, Eric W. "Identity Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications