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-5 of 5 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

A352668 Maximum number of induced copies of the diamond graph K_{1,1,2} in an n-node graph.

Original entry on oeis.org

0, 0, 0, 1, 4, 12, 24, 48, 84, 138, 216, 324, 459, 636, 864, 1152, 1488, 1900, 2400, 3000, 3675, 4470, 5400, 6480, 7668, 9030, 10584, 12348, 14259, 16408, 18816, 21504, 24384, 27576, 31104, 34992, 39123, 43650, 48600, 54000, 59700, 65890, 72600, 79860, 87483, 95742
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 72/125, the inducibility of the diamond graph (Hirst 2014).
It is known that there exists a complete multipartite optimal graph (i.e., an n-node graph with a(n) induced diamond graphs) for all n (Brown and Sidorenko 1994) and that a complete 5-partite graph is asymptotically optimal (Hirst 2014). For 3 <= n <= 7, the 3-partite Turán graph is optimal, and for 7 <= n <= 45, the 4-partite Turán graph is optimal. (For n = 7 both are optimal.) It appears that the 5-partite Turán graph is optimal for all n >= 46 (verified up to n = 75).

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), A352667 (paw graph), A352669 (cycles).

Programs

  • Python
    from sympy.utilities.iterables import combinations,partitions
from sympy.combinatorics import IntegerPartition
f=lambda p:sum(q[0]*q[1]*q[2]*(q[0]+q[1]+q[2]-3)//2 for q in combinations(p,3)) # number of induced diamond graphs in the multipartite graph with parts of sizes given by p
def A352668(n):
    return max(f(IntegerPartition(p).partition) for p in partitions(n))

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

A276401 If n mod 3 = 0 then a(n) = 3^(n/3) + 12*n, if n mod 3 = 1 then a(n) = 4*3^((n-4)/3) + 12*n + 51, otherwise a(n) = 2*3^((n-2)/3) + 12*n - 36.

Original entry on oeis.org

39, 103, 30, 81, 147, 78, 135, 207, 150, 225, 315, 294, 423, 567, 654, 945, 1251, 1662, 2439, 3231, 4614, 6849, 9099, 13398, 20007, 26631, 39678, 59409, 79155, 118446, 177543, 236655, 354678, 531873, 709083, 1063302, 1594791, 2126295, 3189102, 4783473, 6377859
Offset: 3

Views

Author

N. J. A. Sloane, Sep 11 2016

Keywords

Links

Crossrefs

Cf. A352669.

Programs

  • Maple
    f:=n-> if n mod 3 = 0 then 3^(n/3)+12*n
elif n mod 3 = 1 then 4*3^((n-4)/3)+12*n+51
else 2*3^((n-2)/3)+12*n-36; fi;
[seq(f(n),n=3..40)];
  • Mathematica
    CoefficientList[Series[(30 x^6 -223 x^5 + 190 x^4 + 105 x^3 + 73 x^2 - 64 x - 39) / ((x-1)^2 (3 x^3-1) (x^2+x+1)), {x, 0, 33}], x] (* Vincenzo Librandi, Sep 12 2016 *)
Table[Which[Mod[n,3]==0,3^(n/3)+12n,Mod[n,3]==1,4*3^((n-4)/3)+12n+51,True,2*3^((n-2)/3)+12n-36],{n,3,40}] (* Harvey P. Dale, Nov 16 2020 *)

Formula

From Chai Wah Wu, Sep 11 2016: (Start)
a(n) = a(n-1) + 4*a(n-3) - 4*a(n-4) - 3*a(n-6) + 3*a(n-7) for n > 9.
a(n) = 4*a(n-3) - 3*a(n-6) - 72 for n > 8.
G.f.: x^3*(30*x^6 - 223*x^5 + 190*x^4 + 105*x^3 + 73*x^2 - 64*x - 39)/((x - 1)^2*(3*x^3 - 1)*(x^2 + x + 1)). (End)
Showing 1-5 of 5 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.