TOPICS

# 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 , 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 , 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.

## See also

Automorphism Group, Graph Automorphism, Rigid Graph, Symmetric Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Albertson, M. and Collins, K. "Symmetry Breaking in Graphs." Electronic J. Combinatorics 3, No. 1, R18, 17 pp., 1996. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r18.Harary, 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.

Identity Graph

## Cite this as:

Weisstein, Eric W. "Identity Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IdentityGraph.html