OFFSET
1,4
COMMENTS
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.
The proportion of all graphs which are prime (a(n) / 2^(n choose 2)) appears to tend to 1 as n approaches infinity.
LINKS
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 9766535.
Carenne Ludena, Miguel Mendez, Nicolas Bolivar, Modular decomposition of graphs and hierarchical modeling, arXiv:1811.10705 [cs.DM], 2018.
Wikipedia, Modular decomposition
EXAMPLE
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.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Caleb Stanford, Oct 09 2019
EXTENSIONS
a(9)-a(11) (computed with tinygraph) from Falk Hüffner, Oct 11 2019
STATUS
approved