I saw a question on the nauty emailing list without receiving any response, and it's something I've encountered in my own research as well. I am currently interested in graphs with diameter 3.

I would like to generate all graphs on 12 vertices with a fixed diameter using geng. Since when n>11, the number of graphs is too high and using pickg to collect the graphs with given diameter after generating 12 vertices connected graphs taking a long time. (By Suresh E)

For instance, maybe we want to obtain non-isomorphic graphs of order 20 with diameter 3. Perhaps they are not too many, one can hope. The numbers are not documented by Oeis. I just see this Number of trees of diameter 4.

Furthermore, I found a similar but not same question, since the user nomatter just concern about counting not generating: Counting graphs with diameter d


1 Answer 1


About 58% of the graphs on 12 vertices have diameter 3, so filtering a complete generation will be as fast as any. On 20 vertices the fraction has dropped to about 31% but the total is so vast that generation by any method at all is impossible. Generation of graphs with very large diameter, where there are not so many, can be done somewhat more efficiently but there is no wonderful method that I know of.

  • 7
    $\begingroup$ How did you get those percentages? $\endgroup$ Sep 28 at 14:31
  • 3
    $\begingroup$ @SamHopkins I generated a lot of random graphs and tested them. $\endgroup$ Sep 29 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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