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