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.

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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
    Commented Nov 19, 2016 at 14:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .