Program to find connected and non-isomorphic graphs

Hello,

I want to determine the connectivity and isomorphism of the graph and save the connected unlabeled graph in the cell array.

In order to do this, I'm trying to make the program that determines connected and non-isomorphic graphs by defining adjacency matrix.

However, It doesn't seem to be working properly.

Although it can determine adjacency matrix that are connected graphs, it cannot determine adjacency matrix that are non-isomorphic graphs.

Here is the code.

% setting
nd = 4;                                         % Number of nodes
eg = nd*(nd-1)/2;                               % Maximum number of edges
egs = dec2bin(0:2^eg-1)-'0';                    % Combinations of edges 
tri = find(triu(ones(nd), 1));                  % Index of the upper triangle of the adjacency matrix
adj = zeros(nd);                                % Preallocation of adjacency matrix
adjbefore = zeros(nd);                          % Preallocation of adjacency matrix
data = cell(1, 1);                              % Preallocation of the cell array

% Loop to find the first graph and save it in the cell array
index = 1;
for i = 1:2^eg                                  % Repeat for several combinations of edges
    adj(tri) = egs(i,:);                        % Assign combination to the upper triangle
    G = graph(adj, 'upper');                    % Defining a Graph
    if all(~diff(conncomp(G)))                  % If it's connected
        data{index, 1} = vertcat(adj);          % Save the adjacency matrix in the cell array
        index = index + 1;
        if isempty(data{1, 1}) == 0             % Stop the loop if a connected graph is found
            break
        end
    end
end

% A loop that determines whether a graph in the cell array and a graph that just calculated are non-isomorphism
% If they are non-isomorphism, save the graph's adjacency matrix that just calculated
for i = i+1:2^eg                                % Repeat for several combinations of edges
% Determine graph connectivity
    adj(tri) = egs(i,:);                        % Assign combination to the upper triangle
    G = graph(adj, 'upper');                    % Defining a Graph
    if not(all(~diff(conncomp(G))))             % If it's not connected
        continue                                % Skip statements below and repeat next
    else
% Loop to determine isomorphism
        for i2 = 1:index-1
            adjbefore = data{i2, 1};                
            Gbefore = graph(adjbefore, 'upper');      % Access the adjacency matrix in the cell array
            if not(isvector(isomorphism(G, Gbefore))) % If it's non-isomorphism
                data{index, 1} = vertcat(adj);        % Save the adjacency matrix in the cell array
                index = index + 1;
                break                                 % Stop the loop if a non-isomorphic graph is found and repeat next
            end
        end
    end
end

When I set the number of nodes 4, I can get 38 adjacency matrix.

However, according to (Number of Graphs on n unlabelled vertices (yorku.ca)), number of graphs on 4 unlabelled nodes is only 6.

How do I get this program to work properly?

Answer 1

[Christine Tobler]

In the last loop, you are checking if adj is isomorphic to any previous graph. If there is one graph that adj is not isomorphic to, it's added to the list.

However, you want to find out if adj is not isomorphic to any of the graphs in data, not just if it's not isomorphic to at least one of them.

[Gamma1990]

Oops! I was careless.

The program worked well.

Thank you for your help.