cp's OEIS Frontend

A370302 Least number of vertices of a graph that contains an induced cycle of length k_i + 3 for i = 1, 2, ..., where n = 2^k_1 + 2^k_2 + ... is the binary expansion of n.

%I A370302 #10 Feb 16 2024 14:54:46
%S A370302 3,4,5,5,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,8,9,9,
%T A370302 9,9,9,9,9,9,9,9,9,9,9,10,10,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,
%U A370302 10,9,10,10,10,10,10,10,10,10,10,10,10,10,10,10
%N A370302 Least number of vertices of a graph that contains an induced cycle of length k_i + 3 for i = 1, 2, ..., where n = 2^k_1 + 2^k_2 + ... is the binary expansion of n.
%H A370302 Pontus von Brömssen, <a href="/A370302/b370302.txt">Table of n, a(n) for n = 1..1023</a>
%F A370302 a(2^m) = m+3.
%F A370302 a(2^m-1) = A370301(m+2).
%e A370302 For n = 22 = 2^4 + 2^2 + 2^1, the graph should contain induced cycles of lengths 4+3 = 7, 2+3 = 5, and 1+3 = 4. This is achieved by a graph on 8 vertices consisting of a cycle 1-2-...-7-1 together with an 8th vertex with edges to 1, 3, and 5; the induced cycles of lengths 5 and 4 are 1-7-6-5-8-1 and (for example) 1-2-3-8-1. Clearly, 7 vertices is not sufficient, so a(22) = 8.
%Y A370302 Cf. A370301, A370303.
%K A370302 nonn
%O A370302 1,1
%A A370302 _Pontus von Brömssen_, Feb 14 2024