0
$\begingroup$

The simple graphs upto $11$ vertices do not have $5,7,9,...$ automorphisms, in other words, the only odd numbers appearing are $1$ and $3$. Is this true for all graphs ?

Formulated as an existence-question :

  • Is there an odd number $k\ge 5$ and a simple graph G with $|Aut(G)|=k$?

    In particular, is there a simple graph with $5$ automorphisms ?

$\endgroup$
3
$\begingroup$

I found Frucht's theorem on Wikipedia.
http://en.wikipedia.org/wiki/Frucht%27s_theorem
According to this theorem, any finite group occurs as the automorphism group of a finite, undirected graph.

$\endgroup$
  • $\begingroup$ The caley-graphs are mentioned in the proof-idea. Can anything be said about the smallest graph realizing a concrete group ? $\endgroup$ – Peter Oct 29 '14 at 13:26
  • $\begingroup$ Wikipedia states that, starting from the caley-graph, a undirected graph can be constructed with the same automorphism-group, but the description is very abstract and no example is given. $\endgroup$ – Peter Oct 29 '14 at 13:32
1
$\begingroup$

An old paper of Frucht (referenced on the wikipedia page on graph automorphisms) contains the following results (Theorems 3.1 and 3.2):

If $n>2$, then there is a cubic graph $G$ on $6n$ vertices with $\text{Aut}(G)\simeq \mathbb{Z}_n$.

If $n>3$, then there is a graph $G$ on $3n$ vertices with $\text{Aut}(G)\simeq \mathbb{Z}_n$.

Note also that the proofs explicitly constructs the required graph.

$\endgroup$
  • 1
    $\begingroup$ It seems to me that the constraint in the final statement here can be weakened to $n > 1$. The paper mentions that Frucht did not find an example for $n=3$ but, unless I am mistaken, imgur.com/4GmPiIu is an example. (And this construction generalizes to $n>3$, too.) $\endgroup$ – Mees de Vries Oct 29 '14 at 13:51
  • $\begingroup$ Mathworld gave me the desired answer. Start with the n-cycle. Over every edge, construct a rectangular and add an edge in each of these rectangulars. I found out that the edges must be chosen in such a way that they do not share a common vertex. The resulting graph has Z(n) as automorphism group and therefore order n. What remains is to find the smallest CUBIC graph with a given order, which exists due to an extension to Frucht's theorem. $\endgroup$ – Peter Oct 30 '14 at 14:45
  • $\begingroup$ The constructed graph due to mathworld need not be the smallest one. $\endgroup$ – Peter Oct 30 '14 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.