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{‘.

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

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

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