I need to find a list of all connected bipartite graphs on 15 vertices.

http://mapleta.maths.uwa.edu.au/~gordon/remote/graphs/index.html#bips lists all graphs on 14 or fewer number of vertices.

http://oeis.org/A005142 says there are 575 252 112 such graphs.



 geng -bc 15 conbip.g6.txt 

with the program geng from Brendan McKay's nauty package, available from http://cs.anu.edu.au/~bdm/nauty/.

The list of connected bipartite graphs with n = 14 vertices is 74MB compressed and requires a few minutes to generate. The list for n = 15 may take a while to complete and the resulting file will be large.

  • 2
    $\begingroup$ I added the flag for connected graphs, and gave an output filename. I also mentioned output size and calculation time. I deleted my copy of the output since it was too large to justify keeping; I believe it took on the order of an hour to generate. $\endgroup$ – Jack Schmidt Jun 30 '12 at 15:14
  • $\begingroup$ Thank you! this a great tool. for n=15 output is 10.7 GB and it took around 10 minutes [running on 3 cores] $\endgroup$ – Hrant Khachatrian Jul 1 '12 at 8:35

Simple estimation can be made if one considers selected bipartite graph Gi and then counts all the possible non-bipartite graphs that can be made from this graph Gi by adding inner edges in earch part of the graph Gi. So, if number of vortices in one part is x and number of vertices of another part is n-x, then the total number of new graphs for graph Gi is ((a b) being the binomial coefficient) 2^(x 2)*2(n-x 2)-1. After finding the minimum expression for x, the final estimation is that for each bipartite graph there are additional 2^n^2 non-bipartite graphs. So the part of bipartite graphs goes to zer when n goes to infinity.

From this result it is possible to get estimation of the total number of bipartite graphs on n vertices.

There are several article that gives exact computation of number of bipartite graphs, but no explicit formulas are given (found).


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.