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,10

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.

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

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

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.

Example

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

Crossrefs

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

Sequence in context: A041928 A028054 A100789 * A028038 A348266 A025992

Adjacent sequences: A385153 A385154 A385155 * A385157 A385158 A385159

Keyword

nonn,more

Author

Jim Nastos and Clara Elliott, Jul 22 2025

Extensions

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

Status

approved