The Maximum Number of Copies of $K_{r,s}$ in Graphs Without Long Cycles or Paths

Abstract

The circumference of a graph is the length of a longest cycle of it. We determine the maximum number of copies of $K_{r,s}$, the complete bipartite graph with classes sizes $r$ and $s$, in 2-connected graphs with circumference less than $k$. As corollaries of our main result, we determine the maximum number of copies of $K_{r,s}$ in $n$-vertex $P_{k}$-free and $M_k$-free graphs for all values of $n$, where $P_k$ is a path on $k$ vertices and $M_k$ is a matching on $k$ edges.