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

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

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

Table of n, a(n) for n=1..46.

Jason I. Brown and Alexander Sidorenko, The inducibility of complete bipartite graphs, Journal of Graph Theory 18 (1994), 629-645.

James Hirst, The inducibility of graphs on four vertices, Journal of Graph Theory 75 (2014), 231-243.

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
def A352668(n):
    return max(f(IntegerPartition(p).partition) for p in partitions(n))

Crossrefs

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

Sequence in context: A192797 A278355 A160619 * A330011 A132477 A102651

Adjacent sequences: A352665 A352666 A352667 * A352669 A352670 A352671

Keyword

nonn

Author

Pontus von Brömssen, Mar 26 2022

Status

approved