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