A394400 - OEIS

%I #30 Apr 13 2026 09:45:08

%S 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,

%T 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,

%U 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

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

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

%H Thomas Bloom, <a href="https://www.erdosproblems.com/forum/thread/82">Erdős Problem 82</a>.

%H Paul W. Dyson and Brendan D. McKay, <a href="https://arxiv.org/abs/2604.08215">Ramsey numbers for regular induced subgraphs</a>, arXiv:2604.08215 [math.CO] (2026).

%H Erdős problems database contributors, <a href="https://github.com/teorth/erdosproblems/issues/94">Computations of F(n) and t(n) from #82</a>.

%H Brendan McKay, <a href="https://users.cecs.anu.edu.au/~bdm/data/ramsey.html">Ramsey Graphs</a>. See the "Regular induced subgraphs" subsection.

%H S. Fajtlowicz, T. McColgan, T. Read, and W. Staton, <a href="https://combinatorialpress.com/article/ars/Volume%20039/volume-39-paper-15.pdf">Ramsey numbers for induced regular subgraphs</a>, Ars Combinatoria, 39 (1995) 149-154.

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

%t PadRight[{1, 2, 4, 7, 11, 10}, 100] (* _Paolo Xausa_, Mar 21 2026 *)

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

%K nonn

%O 1,2

%A _Brendan McKay_, Mar 19 2026