|
|
A352668
|
|
Maximum number of induced copies of the diamond graph K_{1,1,2} in an n-node graph.
|
|
5
|
|
|
0, 0, 0, 1, 4, 12, 24, 48, 84, 138, 216, 324, 459, 636, 864, 1152, 1488, 1900, 2400, 3000, 3675, 4470, 5400, 6480, 7668, 9030, 10584, 12348, 14259, 16408, 18816, 21504, 24384, 27576, 31104, 34992, 39123, 43650, 48600, 54000, 59700, 65890, 72600, 79860, 87483, 95742
(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 72/125, the inducibility of the diamond graph (Hirst 2014).
It is known that there exists a complete multipartite optimal graph (i.e., an n-node graph with a(n) induced diamond graphs) for all n (Brown and Sidorenko 1994) and that a complete 5-partite graph is asymptotically optimal (Hirst 2014). For 3 <= n <= 7, the 3-partite Turán graph is optimal, and for 7 <= n <= 45, the 4-partite Turán graph is optimal. (For n = 7 both are optimal.) It appears that the 5-partite Turán graph is optimal for all n >= 46 (verified up to n = 75).
|
|
LINKS
|
|
|
PROG
|
(Python)
from sympy.utilities.iterables import combinations, partitions
from sympy.combinatorics import IntegerPartition
f=lambda p:sum(q[0]*q[1]*q[2]*(q[0]+q[1]+q[2]-3)//2 for q in combinations(p, 3)) # number of induced diamond graphs in the multipartite graph with parts of sizes given by p
return max(f(IntegerPartition(p).partition) for p in partitions(n))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|