A394400 Number of graphs with n vertices that have no induced regular subgraph of order 4 or greater.

1, 2, 4, 7, 11, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset

1,2

Comments

a(n) = 0 for all n >= 7.

Links

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

Thomas Bloom, Erdős Problem 82.

Paul W. Dyson and Brendan D. McKay, Ramsey numbers for regular induced subgraphs, arXiv:2604.08215 [math.CO] (2026).

Erdős problems database contributors, Computations of F(n) and t(n) from #82.

Brendan McKay, Ramsey Graphs. See the "Regular induced subgraphs" subsection.

S. Fajtlowicz, T. McColgan, T. Read, and W. Staton, Ramsey numbers for induced regular subgraphs, Ars Combinatoria, 39 (1995) 149-154.

Example

An example on 6 vertices is a triangle with an extra vertex attached to each corner.

Mathematica

PadRight[{1, 2, 4, 7, 11, 10}, 100] (* Paolo Xausa, Mar 21 2026 *)

Crossrefs

Cf. A394573 (for order 4 only), A390919 (for order 5 or greater), A392636 (for order 6 or greater), A394933 (for order 7 and greater).

Sequence in context: A333716 A091263 A101430 * A328418 A249594 A127575

Adjacent sequences: A394397 A394398 A394399 * A394401 A394402 A394403

Keyword

nonn

Author

Brendan McKay, Mar 19 2026

Status

approved