Generating Graphs

Using McKay’s nauty (or technically geng), Patrick computes that there are 567,267,560 connected graphs with order 11, minimum degree 3 and maximum degree 9. Those are the ones we are searching through to find difficult graphs.  For the moment we’ve been generating all these graphs and simply filtering out the graphs which are claw-free or chair-free or skew-star free or p4-free, etc. Now we’re at or near the limit for this approach.

Soon we’ll need to write our own generator to get at the graphs where we don’t know the independence number to be efficiently computable, a generator which produces all and only graphs which are connected, have sufficiently large minimum degree, sufficiently small maximum degree, and an induces claw or a chair or a p4, etc. Writing graph generators is one of the things the group in Ghent does. I am learning a lot about these things on my visit here.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s