[Nauty] isomorphism of graphs generated by geng

[Andrew H]

Gordan,
where would i be able too download this from (download size isn't a problem 
as i've about 400 mb left this month and less than a week to use it)? - i'll 
host it on my wepage at andrewhill.no-ip.org once i get it.

Guenter,

if you have already generated all the k-1 edge, n vertex  graphs, then if 
you remove one edge from any k edge graph it would have to be isomorphic to 
one of the k-1 edge graphs (if you have already generated a complete set.)

This is the approach that i'm taking at the moment:
- taking the output from geng
- removing one edge
- find which of the previous graphs it is isomorphic to
- relable verticies so that it is identical
- relable the removed edge, and add it back in.

in general this would be slow, but dealing with the output of geng, you know 
that you already have a complete set of the graphs, and you don't have to 
reject the many isomorphic copies you get, as geng has already filtered 
them.


does anyone know how to relable 2 isomorphic graphs so they are identical - 
i think nauty should be able to do this, as it generates the conanical form 
- you do that for both, and you should be able to relable one to the other, 
but how do you get the permutation to relable the input graph to the 
concanonised one?

it's nice to see a mailing list with some life :)

thanks for the replies,
Andrew

-------------------
Eagles may soar, but weasels don't get sucked into jet engines



>From: Sterten at aol.com
>Reply-To: nauty-list at cs.anu.edu.au
>To: nauty-list at cs.anu.edu.au
>Subject: Re: [Nauty] isomorphism of graphs generated by geng
>Date: Sun, 26 Jun 2005 07:22:53 EDT
>
>
>In einer eMail vom 26.06.2005 12:05:17 Westeuropäische Sommerzeit schreibt
>Sterten at aol.com:
>
> >you could create the lexicographically minimal graph from each  class.
> >This should ensure that the requirement with the edges is  satisfied.
> >(does it really? delete the last 1 in the upper triangle..will it  work
>always ?)
>
>
>
>
>OK, I see now that it doesn't.
>Deleting the last 1 already fails for K_n, but deleting other edges fails
>also.