Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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