OFFSET
1,5
COMMENTS
The sequence (a(n)/binomial(n,4)) is decreasing for n >= 4 and converges to 3/8, the inducibility of the paw graph (Hirst 2014).
Assuming that the extremal graph is KK(j_1, j_2; k_1, k_2), as defined in the Example section below, for some j_1, j_2, k_1, k_2 (these graphs are asymptotically extremal), the sequence would continue as follows, with a(n) = (binomial(j_1,2)*j_2 + binomial(j_2,2)*j_1)*(k_1 + k_2) + (binomial(k_1,2)*k_2 + binomial(k_2,2)*k_1)*(j_1 + j_2).
n | a(n) | (j_1, j_2), (k_1, k_2)
|(conjectural)|
-------------------------------------------------------
13 316 (2,2), (4,5)
14 440 (2,2), (5,5)
15 590 (2,3), (5,5)
16 780 (3,3), (5,5)
17 1008 (2,3), (6,6), or (3,3), (5,6)
18 1296 (3,3), (6,6)
19 1620 (3,3), (6,7), or (3,4), (6,6)
20 2016 (3,3), (7,7), or (4,4), (6,6)
21 2478 (3,4), (7,7)
22 3024 (4,4), (7,7)
23 3632 (4,4), (7,8)
24 4352 (4,4), (8,8)
25 5152 (4,5), (8,8)
26 6080 (5,5), (8,8)
27 7100 (5,5), (8,9)
28 8280 (5,5), (9,9)
29 9558 (5,6), (9,9)
30 11016 (6,6), (9,9)
31 12600 (5,6), (10,10), or (6,6), (9,10)
32 14400 (6,6), (10,10)
33 16320 (6,6), (10,11), or (6,7), (10,10)
34 18480 (6,6), (11,11), or (7,7), (10,10)
35 20812 (6,7), (11,11)
36 23408 (7,7), (11,11)
37 26166 (7,7), (11,12)
38 29232 (7,7), (12,12)
39 32496 (7,8), (12,12)
40 36096 (8,8), (12,12)
41 39904 (8,8), (12,13)
42 44096 (8,8), (13,13)
43 48516 (8,9), (13,13)
44 53352 (9,9), (13,13)
45 58446 (9,9), (13,14)
46 64008 (9,9), (14,14)
47 69832 (9,10), (14,14)
48 76160 (10,10), (14,14)
49 82800 (9,10), (15,15), or (10,10), (14,15)
50 90000 (10,10), (15,15)
For n > 10, more than one optimal graph of the form KK(j_1, j_2; k_1, k_2) seem to exist exactly when n = 2*m^2 + i, where m >= 3 and i = -1, 1, or 2.
LINKS
James Hirst, The inducibility of graphs on four vertices, Journal of Graph Theory 75 (2014), 231-243.
Falk Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 43e7869.
EXAMPLE
All extremal graphs (i.e., n-node graphs having a(n) induced paw graphs) for 4 <= n <= 12 are listed below. Here, KK(j_1, j_2; k_1, k_2) denotes the complement of the disjoint union of K_{j_1, j_2} and K_{k_1, k_2}.
n = 4: KK(0,1;1,2) (the paw graph);
n = 5: KK(0,1;2,2) (the butterfly graph);
n = 6: KK(0,1;2,3);
n = 7: KK(0,1;3,3), KK(0,2;2,3), and KK(1,1;2,3);
n = 8: KK(0,2;3,3) and KK(1,1; 3,3);
n = 9: KK(0,2;3,4), KK(1,1;3,4), and KK(1,2;3,3);
n = 10: KK(1,2;3,4);
n = 11: KK(1,2;4,4);
n = 12: KK(2,2;4,4).
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Pontus von Brömssen, Mar 26 2022
EXTENSIONS
a(10)-a(12) added using tinygraph by Falk Hüffner, Apr 05 2022
STATUS
approved