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.

  • $\begingroup$ I think you wanted to write that indices $p$ and $q$ are not equal. $\endgroup$ – domotorp Nov 17 '16 at 13:10
  • $\begingroup$ Also, what you are looking for seems to be equivalent to symmetric block designs: en.wikipedia.org/wiki/Block_design#Symmetric_BIBDs $\endgroup$ – domotorp Nov 17 '16 at 13:16
  • $\begingroup$ @domotorp I am not familiar to block design. May you kindly explain how does it help to solve this problem? $\endgroup$ – Dutta Nov 17 '16 at 14:08
  • $\begingroup$ 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. $\endgroup$ – domotorp Nov 17 '16 at 14:10
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ I thought that counting on the vertex subsets, and neighbourhoods of a vertex may be easier to get the appropriate figure. $\endgroup$ – Dutta Nov 19 '16 at 13:10
  • $\begingroup$ 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. $\endgroup$ – Pat Devlin Nov 19 '16 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.