A003400 Number of asymmetric (not necessarily connected) graphs with n nodes.

1, 0, 0, 0, 0, 8, 152, 3696, 135004, 7971848, 805364776, 144123121972

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• hard
• more

Comments

Number of simple graphs g on n nodes with |Aut(g)| = 1.

References

• F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 220, Section P3.4.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Klaus Brockhaus, The 6-node asymmetric graphs
• Zoran Maksimovic, Number of graphs on n nodes whose automorphism group orders are k, n<=11
• Yoav Spector, Moshe Schwartz, Study of potential Hamiltonians for quantum graphity, arXiv:1808.05632 [cond-mat.stat-mech], 2018.
• Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
• Eric Weisstein's World of Mathematics, Graph Automorphism
• Eric Weisstein's World of Mathematics, Identity Graph

Crossrefs

Cf. A124059 (connected simple asymmetric graphs).

Cf. A275867 (disconnected simple asymmetric graphs).

Cf. A000088 (simple graphs).

Programs

nauty

for n in {1..10}; do geng -q ${n} | countg -q -a1 | grep altogether | awk '{print $1}'; done # - Sean A. Irvine, Apr 22 2015

Formula

a(n) = A124059(n) + A275867(n).

Extensions

a(8) and a(9) from Eric W. Weisstein, Jun 09 2004

a(10) and a(11) from Zoran Maksimovic, Vladeta Jovovic, Jan 21 2005

a(12) from Sean A. Irvine, Apr 22 2015