OFFSET

1,5

COMMENTS

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.

LINKS

Chaim Even-Zohar and Nati Linial, A Note on the inducibility of 4-vertex graphs, Graphs and Combinatorics 31 (2015), 1367-1380; arXiv version, arXiv:1312.1205 [math.CO], 2013-2014.

Falk Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 43e7869.

Natasha Morrison and Alex Scott, Maximising the number of induced cycles in a graph, Journal of Combinatorial Theory Series B 126 (2017), 24-61.

EXAMPLE

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.

n = 4: P_4 (self-complementary).

n = 5: C_5 (self-complementary).

n = 6: ECB(1, 1, 1, 1, 2) and its complement.

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

n = 8: The antiprism graph and its complement (the Wagner graph).

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

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 07 2022

STATUS

approved