Re: Need Graph Isomorphism Algorithm De-bunked

Ben Livengood wrote

fgrieu wrote:
An alternative to step 6 is to output the graph in
generic order based on a sort of the results, making
a much shorter and useful representative of the graph's
equivalence class (this has been suggested by Bill Cox).
I however fail to convince myself that this is
equivalent; or that the "compare graph's hash" variant
never falsely declare graphs isomorphic, or that the
"compare sorted graphs" variant never falsely declare
graphs non-isomorphic.

I think it is sufficient to represent the graph over the
equivalence class of its vertices. Let N be the number of
equivalence classes over the vertices in the graph. Let A
be a modified N*N adjacency matrix such that A[i,j] is the
number of edges from vertices in equivalence class i to
vertices in equivalence class j. To handle vertices with
zero degree the original number of vertices will have to
be output as well.


I guess we are talking about equivalence class for the
equivalence relation defined by: "two nodes are equivalent
if the graph's matrix is unchanged by swapping these nodes".

I believe that the proposition stated is false, and propose
two 9-vertices graphs as a counterexample:

0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0
1 0 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 0
1 1 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0
1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0
1 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1
0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1
0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1
0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0

The first graph can be visualized as a cube with 8 vertices
and 12 edges, plus an extra vertex connected to the
4 vertices of the top square of the cube.

The second is identical, except for twisting two vertices
on opposite sides of the bottom square.

Unless I make a mistake, both graphs have 3 equivalence
class: the 4 vertices with 3 edges, the 4 other vertices
connected to any of the previous, and the remaining vertex.
They have the same "modified adjacency matrix", as
defined by Ben Livengood, and number of edges.

Yet the graphs are not isomorphic.


François Grieu

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... The first of the two graphs François Grieu provided in his reply to me ... I think that outputting sorted vertices and an equivalence relation ... and as each vertex is mapped all its neighbors can be ... vertexes to the equivalence class I think it is deterministic and in P. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Ben Livengood wrote: ... graphs" variant never falsely declare graphs non-isomorphic. ... Let N be the number of equivalence classes over ... class i to vertices in equivalence class j. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... graphs" variant never falsely declare graphs non-isomorphic. ... I think it is sufficient to represent the graph over the equivalence ... class i to vertices in equivalence class j. ...
    (sci.crypt)
  • Re: definition of K_n in graph theory
    ... Marc Olschok wrote: ... > 'graphs in vector spaces' etc. ... > of a particular interpretation in the target category. ... gave a definition of K_n as some equivalence class of graphs and taking ...
    (sci.math)