Line Graphs and Double Bonding Systems

After looking at a CDK tool for fixing bond orders for aromatic systems (DeduceBondSystemTool in the smiles package) I wondered if there was a more general approach. That is, the problem is to take a molecular graph with no double bonds and generate all possible double bonded systems.

One possibility might be to first convert the graph (G) into a form known as a line graph (lg(G)) where every vertex in lg(G) is an edge in G. If these vertices are labelled to represent the bond order, then an aromatic system has a particular line graph. For example, here is benzene:

The dashed lines show the construction of the line graph, and the labels '-' and '=' mean single and double. Now obviously, the two resulting graphs are essentially the same, so it would be nice to remove this redundancy. An example of two different bonding systems comes from phenanthrene:

Which is great, but how to generate all non-redundant colorings of the line graphs? Since a line graph is just a graph, it can have a signature, and a signature quotient graph. This can then be colored:


However, in this example it is necessary to 'half-color' some of the vertices of the quotient graph ... which doesn't quite seem to work. The numbers in between the colored quotient graphs show how many line graph vertices are in each of the symmetry classes.

In any case, this is a bit of a toy problem, with only a partial solution, but here is a code repository for a sketch of the code. Note that the algorithm is missing!

Comments