Skip to main content

Tutte's Twist Operation on Cubic Graphs

There is an interesting book by W. T. Tutte called 'Graph Theory as I have known it' which is a cross between a normal mathematical text and a biography. So it's a description of the areas he was interested in, and his theorems. One thing that interested me was the use of a 'twist' operation on cubic graphs like so:

Where for the edge between vertices x and y labelled 'A' we reconnect the surrounding edges to form the arrangement on the right hand side. So detach edge D from y and connect it to x, and vice versa with edge C. The lower part of the picture shows what happens for a loop-edge - it transforms to a multi-edge.

This operation is used on a family of 'base' graphs looking like this:

with the first in the list is a vertexless loop graph - that is, it has no vertices and a single edge. From these base graphs, the twist operation can form any cubic graph. Note that all of Un are cubic with 2n vertices.

For example, from U3 we can get to both of the (simple) graphs with 6 vertices by the following sequence:


In this diagram, the twist is being applied to the red edge, then the blue, then the green, etc. The final step converts the prism (G6) to K3,3 (G7) while the other steps involve non-simple graphs with loops and multiple edges.

One of Tutte's uses for these transformations was to show that the number of 1-factors (perfect matching) J of a graph can be calculated by J(G) + J(GA) = J(H) + J(HA) where GA is a graph with the edge A deleted. So, starting with a base graph U - which has J = 1 except for U0 where J = 2. Then use that value to determine the number of 1-factors in the next graph in the sequence, and so on.

It does make me wonder if there is a way to generate cubic graphs from these base examples, by these twists. From a few simple examples it is clear that there would be a lot of redundancy at the leaves of the generated tree, but possibly that could be handled with canonical path augmentation in some way.

Comments

mario bianchi said…
Awesome work! This post has great reference value. It will absolutely help me in my projects. Thanks for sharing such informative content.

Popular posts from this blog

Adamantane, Diamantane, Twistane

After cubane, the thought occurred to look at other regular hydrocarbons. If only there was some sort of classification of chemicals that I could use look up similar structures. Oh wate, there is . Anyway, adamantane is not as regular as cubane, but it is highly symmetrical, looking like three cyclohexanes fused together. The vertices fall into two different types when colored by signature: The carbons with three carbon neighbours (degree-3, in the simple graph) have signature (a) and the degree-2 carbons have signature (b). Atoms of one type are only connected to atoms of another - the graph is bipartite . Adamantane connects together to form diamondoids (or, rather, this class have adamantane as a repeating subunit). One such is diamantane , which is no longer bipartite when colored by signature: It has three classes of vertex in the simple graph (a and b), as the set with degree-3 has been split in two. The tree for signature (c) is not shown. The graph is still bipartite accordin

Király's Method for Generating All Graphs from a Degree Sequence

After posting about the Hakimi-Havel  theorem, I received a nice email suggesting various relevant papers. One of these was by Zoltán Király  called " Recognizing Graphic Degree Sequences and Generating All Realizations ". I have now implemented a sketch of the main idea of the paper, which seems to work reasonably well, so I thought I would describe it. See the paper for details, of course. One focus of Király's method is to generate graphs efficiently , by which I mean that it has polynomial delay. In turn, an algorithm with 'polynomial delay' takes a polynomial amount of time between outputs (and to produce the first output). So - roughly - it doesn't take 1s to produce the first graph, 10s for the second, 2s for the third, 300s for the fourth, and so on. Central to the method is the tree that is traversed during the search for graphs that satisfy the input degree sequence. It's a little tricky to draw, but looks something like this: At the top

1,2-dichlorocyclopropane and a spiran

As I am reading a book called "Symmetry in Chemistry" (H. H. Jaffé and M. Orchin) I thought I would try out a couple of examples that they use. One is 1,2-dichlorocylopropane : which is, apparently, dissymmetric because it has a symmetry element (a C2 axis) but is optically active. Incidentally, wedges can look horrible in small structures - this is why: The box around the hydrogen is shaded in grey, to show the effect of overlap. A possible fix might be to shorten the wedge, but sadly this would require working out the bounds of the text when calculating the wedge, which has to be done at render time. Oh well. Another interesting example is this 'spiran', which I can't find on ChEBI or ChemSpider: Image again courtesy of JChempaint . I guess the problem marker (the red line) on the N suggests that it is not a real compound? In any case, some simple code to determine potential chiral centres (using signatures) finds 2 in the cyclopropane structure, and 4 in the