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

Author

Caleb Stanford, Oct 09 2019

Keywords

• nonn
• more

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.

Examples

			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.
		

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

Crossrefs

Cf. A006125.

Extensions

a(9)-a(11) (computed with tinygraph) from Falk Hüffner, Oct 11 2019