A Test for non-isomorphism

Proposition 4

Let and be isomorphic graphs and let be the outputs of Refine applied to and respectively.  Then

How to use Proposition 4

In order to establish that graphs are not isomorphic, we apply Refine to each of the two given graphs G and H. If the conclusions of Proposition 4 are not fully satisfied, G and H are not isomorphic.  The usage would be efficient if the partitionings generated by Refine have many partitions of small size.  The ideal situation is when all partitions are of size one.  Such a partitioning reduces the problem to checking just one specific one-to-one mapping.

In order to establish that graphs are isomorphic , we also apply Refine to each of the two given graphs G and H.  If the conclusions of Proposition 4 are satisfied, we try to restore an isomorphic mapping from G onto H, using the properties that are guaranteed by Proposition 4 for every isomorphic mapping.  The usage would be efficient if the partitionings generated by Refine have many partitions of small size.  Again, the ideal situation is when all partitions are of size one.  Such a partitioning reduces the problem to checking just one specific one-to-one mapping.

Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.