%I #6 Feb 14 2024 20:07:47
%S 3,5,6,7,9,10,11,12,13,14,16
%N Least number of vertices of a universal graph for cycles up to length n, i.e., a graph containing induced cycles of lengths 3..n.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Universal_graph">Universal graph</a>.
%F a(n) = A370302(2^(n-2)-1).
%F a(n) <= a(n-1) + 2.
%e In the following table, graphs with a(n) vertices and induced cycles of lengths 3..n are shown. The vertices 1, 2, ..., n constitute an induced cycle; only the additional vertices n+1, ..., a(n) and their lists of neighbors are given.
%e n | a(n) | vertices outside the given induced n-cycle and their neighbors
%e ---+------+---------------------------------------------------------------
%e 3 | 3 | none
%e 4 | 5 | 5:1,2
%e 5 | 6 | 6:1,2,4
%e 6 | 7 | 7:1,2,4
%e 7 | 9 | 8:1,2,4,9; 9:6,8
%e 8 | 10 | 9:1,3,4,10; 10:6,9
%e 9 | 11 | 10:1,5,11; 11:2,5,10
%e 10 | 12 | 11:1,2,4,7; 12:6,9
%e 11 | 13 | 12:1,2,5,6,8; 13:3,11
%e 12 | 14 | 13:1,2,5,7; 14:3,6,8
%e 13 | 16 | 14:1,3,4,7,15; 15:10,14; 16:6,9
%e For n = 7, the graph with a cycle 1-2-...-7-1 and two additional vertices with edges 8-1, 8-2, 8-4, 8-9, and 9-6 contains induced cycles of lengths 3..7: 1-2-8-1, 2-3-4-8-2, 1-7-6-9-8-1 (for example), 1-7-6-5-4-8-1, and 1-2-3-4-5-6-7-1. No such graph with fewer vertices exists, so a(7) = 9.
%Y Cf. A097911, A348638, A370003, A370302.
%K nonn,more
%O 3,1
%A _Pontus von Brömssen_, Feb 14 2024