5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I think you wanted to write that indices $p$ and $q$ are not equal. $\endgroup$
    – domotorp
    Nov 17, 2016 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, 2016 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$
    – Supriyo
    Nov 17, 2016 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, 2016 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$ Nov 17, 2016 at 23:11

1 Answer 1

1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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