

A352666


Maximum number of induced copies of the claw graph K_{1,3} in an nnode graph.


5



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 nnode 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,nk} is one of the two integers closest to n/2  sqrt(3*n/41), and a(n) = binomial(k,3)*(nk) + binomial(nk,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,n2} 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), 629645.


PROG

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


CROSSREFS

Cf. A271713.
Maximum number of induced copies of other graphs: A028723 (4node cycle), A111384 (3node path), A352665 (4node 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



