Automorphism group of a graph

I'm writing an algorithm to compute the automorphism group of a given graph. I wrote the following code which checks whether any permutation of the nodes yields a graph autmorphism. I have tested this code on small sample graphs (the circle graph with 7 vertices in this code for example), and it works fine. But when I try to test it on a (slightly) bigger graph, say, 50 vertices and 150 edges, it takes very long to compute as the number of permutations of n elements is equal to n!. Does anybody have tips for making this code more efficient to make it useful for graphs with 100 vertices or less?

% Number of vertices
numVertices = 7;

% Create an empty graph
G = graph([], []);

% Add edges to form the circle graph
for i = 1:numVertices
    if i == numVertices
        G = addedge(G, i, 1);
    else
        G = addedge(G, i, i+1);
    end
end

% Plot the graph
figure;
h = plot(G, 'Layout', 'force');

% Get the adjacency matrix
adjMatrix = adjacency(G);

% Compute the automorphism group using the adjacency matrix
automorphisms = {};
allPermutations = perms(1:numVertices);

for i = 1:size(allPermutations, 1)
    permVector = allPermutations(i, :);
    permMatrix = zeros(numVertices);
    for j = 1:numVertices
        permMatrix(j, permVector(j)) = 1;
    end
    
    resultMatrix = permMatrix * adjMatrix * permMatrix';
    if isequal(resultMatrix, adjMatrix)
        automorphisms{end+1} = permMatrix;
    end
end

% Convert cell array to matrix format
automorphisms = cat(3, automorphisms{:});

% Display the automorphism group
disp('Automorphism Group Permutations:');
disp(automorphisms);

% Number of automorphisms
numAutomorphisms = size(automorphisms, 3);
disp(['Number of Automorphisms: ', num2str(numAutomorphisms)]);

[Zahid]

I want to generate regular graph of {8,3} tiling in the form of adjacency matrices for large number of vertices say n=10000. Is that possible to do?

Answer 1

[Dheeraj]

Hi,

Your current approach involves trying all permutations of the graph and checking if they preserve the adjacency structure. This approach is inherently expensive, and as you've observed, its runtime grows factorially with the number of vertices.

As computing automorphism group of a given graph is an NP-Complete problem, you could use automorphism libraries like ‘nauty and Traces’ as they are optimised for graph automorphism problems and are efficient than the brute-force methods.

You could refer to this document on ‘nauty and Traces’ for better understanding.

https://pallini.di.uniroma1.it