The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #28 Oct 11 2019 08:39:07
%S 0,0,0,12,192,10800,970080,161310240,49564247040,28687709433600,
%T 31808433385290240
%N Number of labeled prime graphs on n nodes, i.e., graphs with no nontrivial modules when calculating the modular decomposition.
%C A module in a (simple, undirected) graph is a subset S of vertices that are "externally indistinguishable" in the following sense: for all v_1, v_2 in S and v outside of S, v either has an edge to both v1 or v2, or it has an edge to neither of them. a(n) is the number of graphs where the only such modules S are the empty set, the singleton vertices, and the entire set of vertices.
%C The proportion of all graphs which are prime (a(n) / 2^(n choose 2)) appears to tend to 1 as n approaches infinity.
%H F. Hüffner, <a href="https://github.com/falk-hueffner/tinygraph">tinygraph</a>, software for generating integer sequences based on graph properties, version 9766535.
%H Carenne Ludena, Miguel Mendez, Nicolas Bolivar, <a href="https://arxiv.org/abs/1811.10705">Modular decomposition of graphs and hierarchical modeling</a>, arXiv:1811.10705 [cs.DM], 2018.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Modular_decomposition">Modular decomposition</a>
%e a(3) = 0 because there are no prime graphs on 3 vertices. a(4) = 12 because the only prime graph on 4 vertices is a line (path graph P_4), and there are 12 possible labelings of the path graph.
%Y Cf. A006125.
%K nonn,more
%O 1,4
%A _Caleb Stanford_, Oct 09 2019
%E a(9)-a(11) (computed with tinygraph) from _Falk Hüffner_, Oct 11 2019