login
Maximum number of induced copies of the paw graph in an n-node graph.
5

%I #22 Apr 08 2022 11:10:38

%S 0,0,0,1,4,9,18,36,60,97,152,224

%N Maximum number of induced copies of the paw graph in an n-node graph.

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

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

%C n | a(n) | (j_1, j_2), (k_1, k_2)

%C |(conjectural)|

%C -------------------------------------------------------

%C 13 316 (2,2), (4,5)

%C 14 440 (2,2), (5,5)

%C 15 590 (2,3), (5,5)

%C 16 780 (3,3), (5,5)

%C 17 1008 (2,3), (6,6), or (3,3), (5,6)

%C 18 1296 (3,3), (6,6)

%C 19 1620 (3,3), (6,7), or (3,4), (6,6)

%C 20 2016 (3,3), (7,7), or (4,4), (6,6)

%C 21 2478 (3,4), (7,7)

%C 22 3024 (4,4), (7,7)

%C 23 3632 (4,4), (7,8)

%C 24 4352 (4,4), (8,8)

%C 25 5152 (4,5), (8,8)

%C 26 6080 (5,5), (8,8)

%C 27 7100 (5,5), (8,9)

%C 28 8280 (5,5), (9,9)

%C 29 9558 (5,6), (9,9)

%C 30 11016 (6,6), (9,9)

%C 31 12600 (5,6), (10,10), or (6,6), (9,10)

%C 32 14400 (6,6), (10,10)

%C 33 16320 (6,6), (10,11), or (6,7), (10,10)

%C 34 18480 (6,6), (11,11), or (7,7), (10,10)

%C 35 20812 (6,7), (11,11)

%C 36 23408 (7,7), (11,11)

%C 37 26166 (7,7), (11,12)

%C 38 29232 (7,7), (12,12)

%C 39 32496 (7,8), (12,12)

%C 40 36096 (8,8), (12,12)

%C 41 39904 (8,8), (12,13)

%C 42 44096 (8,8), (13,13)

%C 43 48516 (8,9), (13,13)

%C 44 53352 (9,9), (13,13)

%C 45 58446 (9,9), (13,14)

%C 46 64008 (9,9), (14,14)

%C 47 69832 (9,10), (14,14)

%C 48 76160 (10,10), (14,14)

%C 49 82800 (9,10), (15,15), or (10,10), (14,15)

%C 50 90000 (10,10), (15,15)

%C 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.

%H James Hirst, <a href="https://doi.org/10.1002/jgt.21733">The inducibility of graphs on four vertices</a>, Journal of Graph Theory 75 (2014), 231-243.

%H Falk Hüffner, <a href="https://github.com/falk-hueffner/tinygraph">tinygraph</a>, software for generating integer sequences based on graph properties, version 43e7869.

%e 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}.

%e n = 4: KK(0,1;1,2) (the paw graph);

%e n = 5: KK(0,1;2,2) (the butterfly graph);

%e n = 6: KK(0,1;2,3);

%e n = 7: KK(0,1;3,3), KK(0,2;2,3), and KK(1,1;2,3);

%e n = 8: KK(0,2;3,3) and KK(1,1; 3,3);

%e n = 9: KK(0,2;3,4), KK(1,1;3,4), and KK(1,2;3,3);

%e n = 10: KK(1,2;3,4);

%e n = 11: KK(1,2;4,4);

%e n = 12: KK(2,2;4,4).

%Y Maximum number of induced copies of other graphs: A028723 (4-node cycle), A111384 (3-node path), A352665 (4-node path), A352666 (claw graph), A352668 (diamond graph), A352669 (cycles).

%K nonn,hard,more

%O 1,5

%A _Pontus von Brömssen_, Mar 26 2022

%E a(10)-a(12) added using tinygraph by _Falk Hüffner_, Apr 05 2022