A Test for non-isomorphism
Proposition 4
Let
and
be isomorphic graphs and let
be the outputs of Refine applied to
and
respectively. Then
-
-
- and
- for every isomorphic mapping
-
and
- the subgraph of
induced on
is isomorphic to the subgraph
induced on
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.