A385156 The number of undirected, simple, unlabeled graphs G on n vertices which are prime, not split, and do not contain a vertex of degree 1 in G or in the complement of G, and has no induced P5 in G or in the complement of G.

0, 0, 0, 0, 1, 0, 0, 0, 0, 22, 310, 4177

Offset: 1

Author

Jim Nastos and Clara Elliott, Jul 22 2025

Keywords

• nonn
• more

Comments

Here, "prime" means with respect to modular decomposition (see link). A P5 is a path on 5 vertices. A split graph is a graph whose vertices can be partitioned into a clique and an independent set. Related to conjectures in the referenced paper.

Examples

			a(5) = 1 is the C5.
One of the examples of a(10) = 22 is available in the links.
		

References

• Maria Chudnovsky and Peter Maceli, "Simplicial Vertices in Graphs with no Induced Four-Edge Path or Four-Edge Antipath, and the H6-Conjecture," Journal of Graph Theory, vol 76, no 4, (2014).

Links

• Maria Chudnovsky and Peter Maceli, Simplicial Vertices in Graphs with no Induced Four-Edge Path or Four-Edge Antipath, and the H6-Conjecture, arXiv:1302.0404 [math.CO], 2013.
• House of Graphs, One of the 22 graphs on 10 vertices.
• Sean A. Irvine, Java program (github)
• Wikipedia, Modular decomposition.

Crossrefs

Cf. A385697 (when split graph condition is dropped).

Extensions

a(11)-a(12) from Sean A. Irvine, Aug 17 2025