Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!samsung!munnari.oz.au!manuel!csc.anu.edu.au!bdm659
From: bdm659@csc.anu.edu.au
Newsgroups: comp.theory
Subject: Re: GRAPH ISOMORPHISMS !
Message-ID: <1991Apr28.201043.1@csc.anu.edu.au>
Date: 28 Apr 91 09:10:43 GMT
References: <1991Apr24.002002.9063@grape.ecs.clarkson.edu>
Sender: news@newshost.anu.edu.au
Organization: Computer Services, Australian National University
Lines: 20

In article <1991Apr24.002002.9063@grape.ecs.clarkson.edu>, banavana@clutx.clarkson.edu (Narasimhas Banavara) writes:
>       Hi,
>          can someone explain me the "Standard Self-Reducibility"
>       of graphs which enables to search for "an" isomorphism between
>       two graphs G and H given an algorithm which tells us whether
>       the two graphs are "isomorphic".

I don't know what "Standard Self-Reducibility" is, but the task you
require is easy.  Given two isomorphic graphs G and H, "fix" one
vertex v of G by sticking a large clique onto it, making G(v).   Then try
sticking a clique of the same size onto each vertex of H in turn until one
is found, say w, for which the extended graph H(w) is isomorphic to G(v).
Then there must be an isomorphism from G to H taking v onto w.  Continue
in the same way using G(v) and H(w) until an entire isomrphism is found.
The whole process takes O(n^2) isomomorphism tests, where G and H have
n vertices.

>       Narsim.

Brendan.