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

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

Offset: 1

Author

Pontus von Brömssen, Mar 26 2022

Keywords

• nonn
• hard
• more

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.

Examples

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

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.

Crossrefs

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

Extensions

a(10)-a(12) added using tinygraph by Falk Hüffner, Apr 05 2022