In the interest of not publishing false information (even on a blog), this is a brief outline of why the approach outlined in the previous post does not work.
When constructing a set of graphs - from their degree sequences or otherwise - it is usual to describe the process as traversing a tree. The root of the tree is the empty set, and the leaves are the completed graphs. Internal nodes in this tree are partially completed graphs, and parent nodes are connected to children by augmentations.
An augmentation to a graph can be made in various ways: adding a single edge, adding multiple edges to a single new node, etc. However, the important thing is to avoid duplicating solutions at the leaves.
One easy way to do this is to check all newly generated leaves against all the previously generated ones. However, this requires not only storage of all the solutions so far, but also a lot of isomorphism checks. A better way is to check if a solution is canonical by some means. Even better than that is to test the partial graphs (the internal tree nodes) and only follow paths of canonical augmentations.
So this image (click for bigger) shows an example of this failing for the degree sequence [3, 3, 3, 3, 3, 3] (or 36). The first two steps (A, B) are fine : v{0} is connected to v{1,2,3} and then v{1} is connected to v{4,5}. Following the left path, we get to partial graph (C) where v{2} is now connected to v{4,5} - unfortunately the vertices are now no longer in 'degree order'. Compare to the path (B-E-F) on the right to the prism. There, each partial solution has vertices in degree order.
In short, then; canonical augmentation only works if the method to check for a canonical solution is 'aligned' with the augmentation method. When augmenting by saturating orbits, it does not seem possible to use partition refinement to check a graph as canonical, since refinement always starts by partitioning by degree.
When constructing a set of graphs - from their degree sequences or otherwise - it is usual to describe the process as traversing a tree. The root of the tree is the empty set, and the leaves are the completed graphs. Internal nodes in this tree are partially completed graphs, and parent nodes are connected to children by augmentations.
An augmentation to a graph can be made in various ways: adding a single edge, adding multiple edges to a single new node, etc. However, the important thing is to avoid duplicating solutions at the leaves.
One easy way to do this is to check all newly generated leaves against all the previously generated ones. However, this requires not only storage of all the solutions so far, but also a lot of isomorphism checks. A better way is to check if a solution is canonical by some means. Even better than that is to test the partial graphs (the internal tree nodes) and only follow paths of canonical augmentations.
So this image (click for bigger) shows an example of this failing for the degree sequence [3, 3, 3, 3, 3, 3] (or 36). The first two steps (A, B) are fine : v{0} is connected to v{1,2,3} and then v{1} is connected to v{4,5}. Following the left path, we get to partial graph (C) where v{2} is now connected to v{4,5} - unfortunately the vertices are now no longer in 'degree order'. Compare to the path (B-E-F) on the right to the prism. There, each partial solution has vertices in degree order.
In short, then; canonical augmentation only works if the method to check for a canonical solution is 'aligned' with the augmentation method. When augmenting by saturating orbits, it does not seem possible to use partition refinement to check a graph as canonical, since refinement always starts by partitioning by degree.
Comments