TOPICS
Search

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.

IdentityGraphs

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 eight identity graphs of order six (all of which are connected) illustrated above.

IdentityGraphsDisconnected

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.

IdentityGraphsNamed

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

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.

Referenced on Wolfram|Alpha

Identity Graph

Cite this as:

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

Subject classifications