[Nauty-list] geng 33 vertices and diameter 2

[Gunnar Brinkmann]

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