Nauty comes with a pretty good description of the algorithm it uses to solve the graph isomorphism problem and enumerate the graphs. The cube with long diagonals is just K4,4 (a bipartite graph with four nodes on each side and degree four). I'm not sure what you're saying about permutating that matrix; I can permute it (rows and columns identically) into 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 -tom On Thu, Jun 20, 2019 at 8:44 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --