Skip to main content
1 of 2
user119197
  • 675
  • 4
  • 7

minimum value of maximal number of complete bipartite subgraph

We define $F(n,m,k)$ as the family of bipartie graphs $G$ with two disjoint independent (vertex) sets $U$ and $V$ satisfying that

(1) the cardinality of $U$ is $|U|=n$ and the cardinality of $V$ is $|V|=m$.

(2) the valency of each vertex in $U$ is $k$.

We denote $f(G)$ as the maximum number of $pq$ where $G$ contains a complete bipartite graph with two disjoint independent sets $U'$ and $V'$ with $|U'|=p$ and $|V'|=m$. For a triple $(n,m,k)$, we denote $f(n,m,k)$ be the minimum value of $f(G)$ as $G$ ranges over all graphs in $F(n,m,k)$.

I would like to estimate the lower bound for $f(n,m,k)$. Thanks in advance.

user119197
  • 675
  • 4
  • 7