2
$\begingroup$

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.

2 Answers 2

7

Try

 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.

  • 0
    Thank you! this a great tool. for n=15 output is $10$.7 GB and it took around 10 minutes [running on 3 cores]2012-07-01
0

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).