A328261 Number of labeled prime graphs on n nodes, i.e., graphs with no nontrivial modules when calculating the modular decomposition.

0, 0, 0, 12, 192, 10800, 970080, 161310240, 49564247040, 28687709433600, 31808433385290240

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

Table of n, a(n) for n=1..11.

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

Cf. A006125.

Sequence in context: A095351 A061065 A210356 * A264603 A296841 A342111

Adjacent sequences: A328258 A328259 A328260 * A328262 A328263 A328264

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