On The Number Of Labeled Bipartite Graphs

Abstract

Let $I$ and $O$ denote two sets of vertices, where $I\cap O=\varnothing$, $|I|=n$, $|O|=r$, and $B_u(n,r)$ denote the set of unlabeled graphs whose edges connect vertices in $I$ and $O$. Recently, it was established in\cite{atmacaoruc2018} that the following two-sided equality holds, \begin{equation} \label{mainResult} \displaystyle \frac{\binom{r+2^{n}-1}{r}}{n!}\, \le\, |B_u(n,r)|\, \le\, 2\frac{\binom{r+2^{n}-1}{r}}{n!},\, n < r.\nonumber \end{equation} and exact formulas were provided in~\cite{atmaca2017size} for $|B_u(2,r)|$ and $|B_u(3,r)|.$ In this paper, these results are extended to various families of labeled bipartite graphs.

18 pages, 6 figures