Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

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.

share|improve this question

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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