From: bdm@cs.anu.edu.au (Brendan McKay)
Subject: Re: regular rigid graph
Date: Wed, 24 Jan 2001 13:39:33 +1100
Newsgroups: sci.math.research
Summary: Regular graphs with trivial automorphism groups

qcheng <qcheng@pollux.usc.edu> wrote:

> What is the regular graph with fewest nodes which doesn't
> have non-trivial automorphism?

Four regular graphs of order 10 and degree 4.  Plus their complements,
of course.  Here are their edge sets, vertices numbered from 0.

0 4  0 5  0 8  0 9  1 4  1 6  1 7  1 8  2 5  2 6
2 7  2 9  3 6  3 7  3 8  3 9  4 5  4 7  5 9  6 8

0 3  0 5  0 6  0 7  1 4  1 6  1 8  1 9  2 5  2 6
2 7  2 9  3 6  3 8  3 9  4 7  4 8  4 9  5 7  5 8

0 3  0 5  0 7  0 8  1 4  1 5  1 7  1 9  2 5  2 6
2 8  2 9  3 6  3 7  3 8  4 6  4 8  4 9  5 7  6 9

0 3  0 5  0 6  0 7  1 4  1 6  1 8  1 9  2 5  2 6
2 8  2 9  3 5  3 7  3 9  4 7  4 8  4 9  5 8  6 7

Brendan.