%I #16 Apr 07 2022 11:25:15
%S 0,0,0,1,5,9,16,32,48,80,112,160
%N Maximum number of induced copies of the 4-node path in an n-node graph.
%C The sequence (a(n)/binomial(n,4)) is decreasing for n >= 4 and converges to the inducibility of the 4-node path, which is known to be between 1173/5824 = 0.201407... and 0.204513; see Even-Zohar and Linial (2015), who attribute the upper bound to _Emil R. Vaughan_.
%H Chaim Even-Zohar and Nati Linial, <a href="https://doi.org/10.1007/s00373-014-1475-4">A Note on the inducibility of 4-vertex graphs</a>, Graphs and Combinatorics 31 (2015), 1367-1380; <a href="https://arxiv.org/abs/1312.1205">arXiv version</a>, arXiv:1312.1205 [math.CO], 2013-2014.
%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.
%H Natasha Morrison and Alex Scott, <a href="http://dx.doi.org/10.1016/j.jctb.2017.03.007">Maximising the number of induced cycles in a graph</a>, Journal of Combinatorial Theory Series B 126 (2017), 24-61.
%e All optimal graphs (i.e., n-node graphs having a(n) induced copies of P_4) for 4 <= n <= 9 are listed below. Since P_4 is self-complementary, the optimal graphs come in complementary pairs. Here, ECB(n_1, ..., n_k) denotes the empty cyclic braid graph with cluster sizes n_1, ..., n_k, as defined by Morrison and Scott (2017), i.e., the graph obtained by arranging k clusters of n_1, ..., n_k nodes, respectively, in a cycle, and joining all pairs of nodes in neighboring clusters with edges.
%e n = 4: P_4 (self-complementary).
%e n = 5: C_5 (self-complementary).
%e n = 6: ECB(1, 1, 1, 1, 2) and its complement.
%e n = 7: 8 optimal graphs, among them ECB(1, 1, 1, 2, 2) and ECB(1, 1, 2, 1, 2), and their complements. In graph6 format, the optimal graphs are "F?o~_", "FCY^_", "FCpv?", "FCxv?", "FCxvO", "FQjRo", "FQyuo", and "FQyvO".
%e n = 8: The antiprism graph and its complement (the Wagner graph).
%e n = 9: 22 optimal graphs, among them all graphs that are supergraphs of ECB(1, 2, 2, 2, 2) and subgraphs of its complement (10 graphs altogether), and the 1-skeletons of the Johnson solids J10 (the gyroelongated square pyramid) and J51 (the triaugmented triangular prism) and their complements. In graph6 format, the optimal graphs are "H?bF`xw", "H?o}^_}", "H?o}^bp", "H?q`qjo", "H?q`v`[", "H?rF`zo", "H?rF`zq", "HCRbdO{", "HCXfczo", "HCXfczq", "HCXk~a]", "HCXk~bo", "HCXk~bp", "HCY^fXy", "HCrb`qi", "HCrb`rc", "HEhuTxm", "HEhutxm", "HQjUjqm", "HQyurjU", "HQyurji", and "HQyurzU".
%Y Maximum number of induced copies of other graphs: A028723 (4-node cycle), A111384 (3-node path), A352666 (claw graph), A352667 (paw 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 07 2022