# All Bipartite Graphs on n number of vertices

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.

-

## 1 Answer

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.

-
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. –  Jack Schmidt Jun 30 '12 at 15:14
Thank you! this a great tool. for n=15 output is 10.7 GB and it took around 10 minutes [running on 3 cores] –  Hrant Khachatrian Jul 1 '12 at 8:35