cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A352666 Maximum number of induced copies of the claw graph K_{1,3} in an n-node graph.

Original entry on oeis.org

0, 0, 0, 1, 4, 10, 20, 40, 70, 112, 176, 261, 372, 520, 704, 935, 1220, 1560, 1976, 2464, 3038, 3710, 4480, 5376, 6392, 7548, 8856, 10320, 11970, 13800, 15840, 18095, 20580, 23320, 26312, 29601, 33176, 37072, 41300, 45875, 50830, 56160, 61920, 68096, 74732
Offset: 1

Views

Author

Pontus von Brömssen, Mar 26 2022

Keywords

Comments

The sequence (a(n)/binomial(n,4)) is decreasing for n >= 4 and converges to 1/2, the inducibility of the claw graph.
Brown and Sidorenko (1994) prove that a bipartite optimal graph (i.e., an n-node graph with a(n) induced claw graphs) exists for all n. For n >= 2, the size k of the smallest part of an optimal bipartite graph K_{k,n-k} is one of the two integers closest to n/2 - sqrt(3*n/4-1), and a(n) = binomial(k,3)*(n-k) + binomial(n-k,3)*k. Both are optimal if and only if n is in A271713. For 7 <= n <= 10 (and, trivially, n = 3), the tripartite graph K_{1,1,n-2} is also optimal.

Links

Crossrefs

Cf. A271713.
Maximum number of induced copies of other graphs: A028723 (4-node cycle), A111384 (3-node path), A352665 (4-node path), A352667 (paw graph), A352668 (diamond graph), A352669 (cycles).

Programs

  • Python
    from math import comb,isqrt
def A352666(n):
    if n <= 1: return 0
    r = isqrt(3*n-4)
    k0 = (n-r-1)//2
    return max(comb(k,3)*(n-k)+comb(n-k,3)*k for k in (k0,k0+1))

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

Original entry on oeis.org

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

Views

Author

Pontus von Brömssen, Mar 26 2022

Keywords

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

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

A352669 Maximum number of induced cycles in an n-node graph.

Original entry on oeis.org

0, 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 225
Offset: 1

Views

Author

Pontus von Brömssen, Mar 26 2022

Keywords

Comments

For 3 <= n <= 11, a(n) = binomial(n,3) = A000292(n-2) and the complete graph is the unique extremal graph, but a(12) = 225 > binomial(12,3), where the unique extremal graph is K_{6,6}.
Morrison and Scott (2017) prove that, for sufficiently large n (they say it ought to be true for n >= 30), a(n) = A276401(n), with the unique extremal graph being the empty cyclic braid graph with one cluster of size 4 if n == 1 (mod 3), one cluster of size 2 if n == 2 (mod 3), and all other clusters of size 3. (The empty cyclic braid graph is obtained by arranging clusters of nodes of the appropriate sizes in a cycle and joining all pairs of nodes in neighboring clusters with edges.) For 14 <= n <= 21, this graph is not extremal, because the balanced bipartite graph K_{floor(n/2),ceiling(n/2)} has A028723(n+1) > A276401(n) induced cycles.

Links

Crossrefs

Cf. A000292, A028723, A276401.
Maximum number of induced copies of other graphs: A028723 (4-node cycle), A111384 (3-node path), A352665 (4-node path), A352666 (claw graph), A352667 (paw graph), A352668 (diamond graph).

Extensions

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

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

Original entry on oeis.org

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

Views

Author

Pontus von Brömssen, Mar 26 2022

Keywords

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.

Examples

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

Links

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

Extensions

a(10)-a(12) added using tinygraph by Falk Hüffner, Apr 07 2022
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.