[Nauty-list] Nauty-list Digest, Vol 38, Issue 2

Brendan McKay bdm at cs.anu.edu.au
Sat Jul 25 19:49:19 EST 2009


For each self-complementary graph G there is a permutation p such
that p maps G onto its complement, p has at most 1 fixed point, and
the order of p is a power of 2 at least 4. This is (easy) theory.
I just took all the possible cycle structures for p, made all the
graphs G for which p maps G onto its complement (with a little
isomorph reduction built in) and removed remaining isomorphs.

The same method with more sophistication was used by McNally and
Molina in the mid 1990s to make the s-c up to order 17.  I didn't
bother with the niceties since computers are now so fast that
the time saved would have not justified the programming effort.

Brendan.

* Sahil Singla <sahilsingla81 at gmail.com> [090725 15:31]:
> Hello
> What is the algorithm used to generate the listing of self complementary
> graphs given on http://cs.anu.edu.au/~bdm/data/graphs.html
> 
> Thanks
> Sahil
> 
> On Sat, Jul 25, 2009 at 7:30 AM, <nauty-list-request at cs.anu.edu.au> wrote:
> 
> > Send Nauty-list mailing list submissions to
> >        nauty-list at cs.anu.edu.au
> >
> > To subscribe or unsubscribe via the World Wide Web, visit
> >        http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
> > or, via email, send a message with subject or body 'help' to
> >        nauty-list-request at cs.anu.edu.au
> >
> > You can reach the person managing the list at
> >        nauty-list-owner at cs.anu.edu.au
> >
> > When replying, please edit your Subject line so it is more specific
> > than "Re: Contents of Nauty-list digest..."
> >
> >
> > Today's Topics:
> >
> >   1. question (Sam Speed)
> >   2. Re: question (Brendan McKay)
> >
> >
> > ----------------------------------------------------------------------
> >
> > Message: 1
> > Date: Fri, 24 Jul 2009 09:34:10 -0500 (CDT)
> > From: Sam Speed <speeds at msci.memphis.edu>
> > Subject: [Nauty-list] question
> > To: nauty-list at cs.anu.edu.au
> > Message-ID: <Pine.GSO.4.61.0907240932320.3827 at prolog>
> > Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
> >
> >
> > Is there a listings (in nauty graph6 format) of the 720 self-complement
> > graphs on 12 vertices?
> >
> > Thanks
> >
> > Sam Speed
> >
> >
> >
> > ------------------------------
> >
> > Message: 2
> > Date: Sat, 25 Jul 2009 01:23:33 +1000
> > From: Brendan McKay <bdm at cs.anu.edu.au>
> > Subject: Re: [Nauty-list] question
> > To: Sam Speed <speeds at msci.memphis.edu>
> > Cc: nauty-list at cs.anu.edu.au
> > Message-ID: <20090724152333.GA17757 at cs.anu.edu.au>
> > Content-Type: text/plain; charset=us-ascii
> >
> > http://cs.anu.edu.au/~bdm/data/graphs.html<http://cs.anu.edu.au/%7Ebdm/data/graphs.html>
> >
> > Cheers, Brendan.
> >
> > * Sam Speed <speeds at msci.memphis.edu> [090725 00:18]:
> > >
> > > Is there a listings (in nauty graph6 format) of the 720 self-complement
> > > graphs on 12 vertices?
> > >
> > > Thanks
> > >
> > > Sam Speed
> > >
> > > _______________________________________________
> > > Nauty-list mailing list
> > > Nauty-list at cs.anu.edu.au
> > > http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
> >
> >
> >
> > ------------------------------
> >
> > _______________________________________________
> > Nauty-list mailing list
> > Nauty-list at cs.anu.edu.au
> > http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
> >
> >
> > End of Nauty-list Digest, Vol 38, Issue 2
> > *****************************************
> >

> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list





More information about the Nauty mailing list