# Number of bipartite graphs with a neighborhood property

Consider a bipartite graph of order $2n$ with equal bipartitions $C_1$ and $C_2$, where, $$C_i = \{v_{i,1}, v_{i,2}, v_{i,3} \dots v_{i,n}\}; i = 1, 2.$$ Given two vertices $v_{i,p}$ and $v_{i,q}$, $Nbd(v_{i,p}, v_{i,q})$ denotes set vertices adjacent to both $v_{i,p}$ and $v_{i,q}$ with $1 \le p,q \le n$. Indexes $p$ and $q$ may or may not be equal. We denote cardinallity of $Nbd(v_{i,p}, v_{i,q})$ by $\#(Nbd(v_{i,p}, v_{i,q}))$.

I want to calculate number of bipartite graphs, such that, $$\#(Nbd(v_{1,p}, v_{1,q})) = \#(Nbd(v_{2,p}, v_{2,q})) ~\forall~ p,q ~\text{with}~ 1 \le p,q \le n.$$

To construct all these graphs, I am also looking for an existing algorithm, if available.

• I think you wanted to write that indices $p$ and $q$ are not equal. – domotorp Nov 17 '16 at 13:10
• Also, what you are looking for seems to be equivalent to symmetric block designs: en.wikipedia.org/wiki/Block_design#Symmetric_BIBDs – domotorp Nov 17 '16 at 13:16
• @domotorp I am not familiar to block design. May you kindly explain how does it help to solve this problem? – Dutta Nov 17 '16 at 14:08
• I'm also no expert on the topic, and I doubt that I could add much to the Wikipedia article; obviously $C_1$ would play the role of the blocks, and $C_2$ the role of the points. – domotorp Nov 17 '16 at 14:10
• A symmetric BIBD is the special case where all the common-neighbour counts are the same. The description here is more general. Assuming you include $p=q$ in your definition, what you want is the set of all $n\times n$ binary matrices $B$ such that $BB^T=B^TB$. Offhand I don't recall anything on that. – Brendan McKay Nov 17 '16 at 23:11

As noted in the comments, if $B$ is the bipartite adjacency matrix (so that $b_{i,j}$ is 1 if $v_{1, i} \sim v_{2, j}$ and $0$ otherwise), then your condition is equivalent to saying that $B B^T - B^T B$ is diagonal. I'll assume that you also intend to insist that your property holds for $p=q$, which implies $B B^T = B^T B$. This is not a symmetric block design
Therefore, the number of ${0,1}$ matrices with this property is what you want. This number is bounded below by the number of symmetric ${0,1}$ matrices, which is $2^{n(n+1)/2}$. This is not the entire picture since (for example) we could also take any permutation matrix. But I would be surprised if the answer is noticeably larger than that, and this enormous lower bound shows that any algorithm to list all such objects is doomed to be extremely slow.
• The lower bound I gave is about $\sqrt{2}^{n^2}$, and the trivial upper bound is $2^{n^2}.$ I don't expect the base of the exponent could be improved. – Pat Devlin Nov 19 '16 at 14:47