|
%I #11 Apr 02 2022 10:37:23
%S 0,0,0,1,4,10,20,40,70,112,176,261,372,520,704,935,1220,1560,1976,
%T 2464,3038,3710,4480,5376,6392,7548,8856,10320,11970,13800,15840,
%U 18095,20580,23320,26312,29601,33176,37072,41300,45875,50830,56160,61920,68096,74732
%N Maximum number of induced copies of the claw graph K_{1,3} in an n-node graph.
%C The sequence (a(n)/binomial(n,4)) is decreasing for n >= 4 and converges to 1/2, the inducibility of the claw graph.
%C 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.
%H Jason I. Brown and Alexander Sidorenko, <a href="https://doi.org/10.1002/jgt.3190180610">The inducibility of complete bipartite graphs</a>, Journal of Graph Theory 18 (1994), 629-645.
%o (Python)
%o from math import comb,isqrt
%o def A352666(n):
%o if n <= 1: return 0
%o r = isqrt(3*n-4)
%o k0 = (n-r-1)//2
%o return max(comb(k,3)*(n-k)+comb(n-k,3)*k for k in (k0,k0+1))
%Y Cf. A271713.
%Y 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).
%K nonn
%O 1,5
%A _Pontus von Brömssen_, Mar 26 2022
|
