login
Maximum number of induced copies of the diamond graph K_{1,1,2} in an n-node graph.
5

%I #10 Apr 02 2022 10:37:17

%S 0,0,0,1,4,12,24,48,84,138,216,324,459,636,864,1152,1488,1900,2400,

%T 3000,3675,4470,5400,6480,7668,9030,10584,12348,14259,16408,18816,

%U 21504,24384,27576,31104,34992,39123,43650,48600,54000,59700,65890,72600,79860,87483,95742

%N Maximum number of induced copies of the diamond graph K_{1,1,2} in an n-node graph.

%C 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).

%C 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).

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

%H James Hirst, <a href="https://doi.org/10.1002/jgt.21733">The inducibility of graphs on four vertices</a>, Journal of Graph Theory 75 (2014), 231-243.

%o (Python)

%o from sympy.utilities.iterables import combinations,partitions

%o from sympy.combinatorics import IntegerPartition

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

%o def A352668(n):

%o return max(f(IntegerPartition(p).partition) for p in partitions(n))

%Y Maximum number of induced copies of other graphs: A028723 (4-node cycle), A111384 (3-node path), A352665 (4-node path), A352666 (claw graph), A352667 (paw graph), A352669 (cycles).

%K nonn

%O 1,5

%A _Pontus von Brömssen_, Mar 26 2022