0
$\begingroup$

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'|=q$. For a triple $(n,m,k)$, we denote by $f(n,m,k)$ 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.

Improve this question
$\endgroup$
2
  • $\begingroup$ We have $f(n, m, k)\geqslant \max(k,kn/m) $ that corresponds to $\min(p, q)=1$. I expect this to be tight for not too large $k$. $\endgroup$
    – Fedor Petrov
    Commented May 4 at 12:54
  • $\begingroup$ You changed notation from $(n, m)$ to $(p, q)$ for the cardinality of the ‘parts’, and I think in one place made an accidental inconsistency: $f(G)$ maximises $p q$, but you had $\lvert V'\rvert = m$. I edited to require $\lvert V'\rvert = q$, as the context suggested. I hope that this was all right. \\ When defining $f(n, m, k)$, you do not want to require that $p = n$ or $q = m$, or that each vertex of $U'$ have degree $k$? $\endgroup$
    – LSpice
    Commented May 4 at 14:35

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .