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.
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, 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, 10, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Offset: 1
Keywords
Examples
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.
Links
- Pontus von Brömssen, Table of n, a(n) for n = 1..1023
Formula
a(2^m) = m+3.
a(2^m-1) = A370301(m+2).