Skip to main content
Typos
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

minimum Minimum value of maximal number of complete bipartite subgraphsubgraphs

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

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

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.

Minimum value of maximal number of complete bipartite subgraphs

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.

Source Link
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.