Skip to main content

Posts

Showing posts from August, 2011

McKay's canonical augmentation method explained for simple graphs

The previous post talked about generating one type of combinatorial object (chessboards) using a method similar to that outlined by Brendan McKay in a paper called "Isomorph-free exhaustive generation" (J Algorithms, 26 (1998) 306-324.). This one will focus instead on simple graphs, which requires both parts of the method.The canonical construction (or canonical augmentation) method has two components. Firstly, only one 'expansion' of a graph is tried at each step from the set of equivalent expansions. Secondly, the expansions are checked to see if they are the inverse of a 'canonical deletion' for that graph.For an example of the first rule, consider this set of expansions of a 4-vertex graph on the left:Each of the 5-vertex graphs on the right are shown with the newly added vertex and edges in red; the arrows are labelled by the added edge set - so {1:4, 3:4} means edges added from 1 to 4 and 3 to 4. The sets of vertices to add to - {{0}, {1}, {1,3}} - are …

Generating Chessboards With K-Independant Vertex Sets

After looking at Julio Peironcely's poster on generating chemical structures, where he describes using Canonical Path Augmentation (I think due to Brendan McKay) I went looking for more about it. One thing I found was this talk/slideshow by Mathieu Dutour Sikirić - incidentally coauthor of a nice book on Chemical Graphs.
Anyway; that's the context. Now : about chessboards? Well one of the examples given for augmentation (or 'orderly') schemes of independent vertex sets. I'm not sure what made me think of chessboards for this, but I think it's a fairly standard simple toy example. Let me show an example for 3x3 boards:
So, these are all the three by three boards where no two black squares share an edge. In other words, if the board is considered as a grid-shaped graph, then these are the k-independent vertex sets. So the question is : how to generate these?
The simple way, of course, is just to fill in every square and eliminate those boards that have pairs of blac…