4
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 7
    $\begingroup$ How did you get those percentages? $\endgroup$
    – Sam Hopkins
    Commented Sep 28, 2023 at 14:31
  • 3
    $\begingroup$ @SamHopkins I generated a lot of random graphs and tested them. $\endgroup$
    – Brendan McKay
    Commented Sep 29, 2023 at 11:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .