[Nauty-list] geng 33 vertices and diameter 2
Gunnar Brinkmann
Gunnar.Brinkmann at ugent.be
Wed Oct 19 18:26:01 EST 2005
Hoang Minh Nguyen wrote:
>Hi everyone,
>
> At the moment geng is limited to generating graphs of order up to
>32. It seems that this restriction is due to the data structure used to
>store intermediate graphs?
>
>I would like to know if there is a way to modify geng to generate ALL graphs
>of order 33 with the restriction that the diameter of each graph is 2.
>
>Is there a good way to speed up the search given the diameter restriction?
>
>It might be a hard problem but just ask in case someone has any idea :-).
>
>
There is a special programn that generates diameter 2 graphs if you have
the additional
restriction that they are triangle free. But even with this additional
restriction there are
__FAR__ too many to generate them all.
Just think about the following: take an arbitrary graph with n vertices
and add a new
vertex neighbouring all of the previous n vertices. This is a diameter 2
(or 1) graph on n+1
vertices. I'm not talking about isomorphism here, but it gives you an
idea that restricting
the diameter to 2 doesn't help you get much further than when generating
all graphs.
Gunnar
--
Gunnar Brinkmann
Applied Mathematics and Computer Science
Ghent University
Krijgslaan 281 - S9
B - 9000 Ghent
email: Gunnar.Brinkmann at UGent.be
phone: +32-9-264.48.07, Fax: +32-9-264.49.95
More information about the Nauty
mailing list