Sage, Grinvin, and Graph6

The last difficult graph had the property of having adjacent twin vertices. So one of these can be removed in a search for a maximum independent set. More generally, if there are vertices v and w with N[w] a subset of N[v], then v can be removed (see Fomin, et al). I added this property to the code. The last “difficulty” has been resolved and we will see what the next difficult graph is.

Before I recognized this, I exported the graph in graph6 (g6) format from Sage (we’re writing all the code in the Sage environment which has very nice built-in graph library). Given a graph G, G.graph6_string exports a string representing G. This string can then be imported into the Grinvin graph exploration program, where you can visualize the graph, and get a table of values of invariants for a large number of invariants a user might be interested in.

Grinvin was designed by a team at the University of Ghent for graph exploration. It also has a conjecture-making module. So if you are interested in automated conjecture-making, this is one tool that you can play with (it is open source and freely available).

Here’s the next difficult graph:

This graph has residue=2, alpha=3, even-even horizontal=3, and cvetkovic=4. Its graph6 string is ‘HCRbdq{‘.


3 thoughts on “Sage, Grinvin, and Graph6

  1. Pingback: Characterizing graphs where alpha = even-minus-even-horizontal | The Independence Number Project

  2. Pingback: Lovasz Number to the rescue | The Independence Number Project

  3. Pingback: INP code available on Github | The Independence Number Project

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