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

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

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

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

Jason I. Brown and Alexander Sidorenko, The inducibility of complete bipartite graphs, Journal of Graph Theory 18 (1994), 629-645.

Prog

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

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

Sequence in context: A038421 A049032 A100354 * A275358 A048008 A048019

Adjacent sequences: A352663 A352664 A352665 * A352667 A352668 A352669

Keyword

nonn

Author

Pontus von Brömssen, Mar 26 2022

Status

approved