A352665 Maximum number of induced copies of the 4-node path in an n-node graph.

0, 0, 0, 1, 5, 9, 16, 32, 48, 80, 112, 160

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

Table of n, a(n) for n=1..12.

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

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

Sequence in context: A090990 A225605 A088495 * A218611 A208669 A062777

Adjacent sequences: A352662 A352663 A352664 * A352666 A352667 A352668

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