On The Number of Unlabeled Bipartite Graphs

Loading...
Thumbnail Image

Publication or External Link

Date

2016

Advisor

Citation

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!} $

Notes

This paper describes a result that has been obtained in joint work with Abdullah Atmaca of Bilkent University, Ankara, Turkey

Rights