On The Number of Unlabeled Bipartite Graphs

Abstract

Let $I$ and $O$ denote two sets of vertices, where $I\cap O =\Phi$, $|I| = n$, $|O| = r$, and $B_u(n,r)$ denote the set of unlabeled graphs whose edges connect vertices in $I$ and $O$. It is shown that the following two-sided equality holds. $\displaystyle \frac{\binom{r+2^{n}-1}{r}}{n!} \le |B_u(n,r)| \le 2\frac{\binom{r+2^{n}-1}{r}}{n!} $