The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A352666 Maximum number of induced copies of the claw graph K_{1,3} in an n-node 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 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 25 09:47 EDT 2023. Contains 361520 sequences. (Running on oeis4.)