A370301 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.

3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 16

Offset: 3

Author

Pontus von Brömssen, Feb 14 2024

Keywords

• nonn
• more

Examples

			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.
   n | a(n) | vertices outside the given induced n-cycle and their neighbors
  ---+------+---------------------------------------------------------------
   3 |   3  | none
   4 |   5  | 5:1,2
   5 |   6  | 6:1,2,4
   6 |   7  | 7:1,2,4
   7 |   9  | 8:1,2,4,9; 9:6,8
   8 |  10  | 9:1,3,4,10; 10:6,9
   9 |  11  | 10:1,5,11; 11:2,5,10
  10 |  12  | 11:1,2,4,7; 12:6,9
  11 |  13  | 12:1,2,5,6,8; 13:3,11
  12 |  14  | 13:1,2,5,7; 14:3,6,8
  13 |  16  | 14:1,3,4,7,15; 15:10,14; 16:6,9
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.
		

Links

• Wikipedia, Universal graph.

Crossrefs

Cf. A097911, A348638, A370003, A370302.

Formula

a(n) = A370302(2^(n-2)-1).

a(n) <= a(n-1) + 2.