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