Tomas Rokicki <rokicki@gmail.com> wrote:
To generate inequivalent graphs, use either genreg or nauty/geng; either should work fine (although I find genreg to be faster, even though nauty is better known).
Thanks, but I was looking for an algorithm I can include in my own program. I would be curious how many unlabeled (i.e. inequivalent) 8-vertex 16-edge graphs those find, however. Thanks. I did notice an interesting coincidence. The adjacency matrix (which is how I represent these graphs) is 8x8, the size of a chessboard. And to represent a 16-game tournament, I need 32 markers, the same number as there are chess pieces. Also, relabeling a graph, which is done by permuting the rows and columns in the same way, preserves the number of pieces on the white squares (hence also the number of pieces on the dark squares). (I'm not certain that those numbers aren't always equal to each other, however.) The adjacency matrix of Dan's graph of a cube with its body diagonals looks interesting: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 It's unchanged under permuting the rows and columns in the same way. Is the same true of any other 8x8 symmetrical matrix with half the entries being 0 and the other half 1? (Other than the complement of this matrix, which is uninteresting for our purposes for obvious reasons.) And the pattern of 0s and 1s read left to right top to bottom I instantly recognized as the first 64 terms of the Thue-Morse sequence.