Some Stuff

Very occasionally there is a question on math stack exchange that I can actually give some kind of useful answer to. This question  caught my eye; the questioner asks whether graphs with the same degree sequence have the same biconnectivity property. Or to put it another way, are there any pairs of graphs with the same degree sequence but one is biconnected and the other is not? I thought of an example of such a pair, and another user supplied a much simpler one, but here are both pairs: The vertices are coloured by degree (4 = orange, 3 = blue, 2 = green); the red arrows show a transformation of the top graph into its non-biconnected partner. Obviously there may be more than one, I've no idea how many members of a set of isodegree graph might be expected to be biconnected. For the record, here is the transformation of the bottom pair: The red lines bisecting edges indicate a kind of 'bond breaking' although it's not meant to represent an actual chemical r...

So another lesson reluctantly learned... It seems the naïve approach to augmenting molecules by sets of bonds (colored edges, strictly rather than multiple edges) did not work. For example this pair of C9H16 graphs: Thicker lines represent double bonds, and the thinner are singles. The parents of these are non-isomorphic - which is easy to see if you just remove the 6:8 edge from both. However, they cannot be distinguished as augmentations by my current method as the canonical labelling each one gives a graph where the last bond added is the 'natural' canonical choice. The alternative might be to use the canonical labelling method for multigraphs suggested by the  nasty  manual which involved transforming the multiedge graph into a layered simple graph. This is illustrated in this example: The transformation converts single edges into an edge in the first layer, and multiple edges into an edge in the second layer (and so on). Highlighted in purple is an example ...

My newest version of canonical path augmentation code for generating graphs has reached a new high point - generating 11,716,571 graphs on ten vertices. Of course, it also gets the number of nines (261,080) and the number of eights (11,117) correct as well ... which is great, but I'm cautious about declaring it 'correct'. Especially given the last version  did not get the sevens and eights right. See, for example these past failures: So how does it get the right answer? Well, it now properly uses the method mentioned in this post  to only pick canonical deletions that are not cut-vertices . That turns out only to be necessary for graphs on 8 vertices, but you still have to check this for all augmentations, which seems expensive. However, there was a more fundamental problem; consider the example below (basically nicked from Derick Stolee 's blog post): Obviously A and B are isomorphic, yet how do we properly distinguish them? Well, the key is the set of vert...