Do there exist asymmetric hamiltonian graphs?

Question

A graph is asymmetric if its automorphism group is trivial. I have tried to create some (very small) hamiltonian graphs but it seems non trivial to force them to be asymmetric.

Answer 1

Yes, there do. Here is an example. Arrange vertices numbered 1 to 7 cyclically, so that 7 connects back to 1. Now add edges (1, 3), (1, 4), (2, 5), (2, 6), (2, 7).

Proof that the automorphism group is trivial: Vertex 1 is the only vertex of degree 4, and vertex 2 is the only vertex of degree 5, so these vertices are fixed by any automorphism. Vertex 4 is also fixed by the condition of being adjacent to 1 but not to 2. Vertex 3 is uniquely adjacent to 1 and 4, so it is fixed. Vertex 5 is the only one left that is adjacent to 4, so it is fixed, and similar arguments apply to 6 and 7.

Answer 2

Here is an asymmetric Hamiltonian graph with $6$ vertices and $8$ edges.

Start with a $C_6$ graph with vertices $v_0,v_1,v_2,v_3,v_4,v_5$ and edges $v_0v_1,v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_0$. Now add two more edges $v_0v_2$ and $v_0v_3$.

The graph is obviously Hamiltonian.

To see that it has no automorphism, observe that
$v_0$ is the only vertex of degree $4$,
$v_4$ is the only vertex not adjacent to $v_0$,
$v_5$ is the only vertex of degree $2$ adjacent to $v_4$,
$v_3$ is the other vertex adjacent to $v_4$,
$v_2$ is the remaining vertex of degree $3$, and
$v_1$ is the only vertex left.

Alternatively, it's easy to see that the $C_6$ we started with is the only Hamiltonian cycle, so an automorphism must fix that cycle; the vertex $v_0$ must be fixed because of its degree; and reversing the cycle obviously doesn't work with the extra edges.