Is there some sort of characterization of all such numbers $n$, that there exists a cubic graph with $2n$ vertices and no non-trivial automorphisms.

Frucht theorem states, that any finite group is an automorphism group of some cubic groups. In particular case, the minimal cubic graph with trivial automorphism group is called Frucht graph and has $12$ vertices. However, I do not know, of what size can the larger examples be...

  • $\begingroup$ If you replace every vertex with a triangle, it seems like the automorphism group might stay trivial and the number of vertices is $3n$. $\endgroup$ – Santana Afton Jul 29 at 13:16
  • $\begingroup$ I'm fairly sure that there are only finitely many even number with so such example. Finding a construction is probably a bit messy but not too hard. Do you really need a full characterization, or arbitrarily large examples would suffice? $\endgroup$ – verret Jul 30 at 3:11
  • $\begingroup$ @verret, arbitrary large examples will already make a good answer. However, the full characterization is also an interesting question... Anyway, I will upvote and accept either of these. $\endgroup$ – Yanior Weg Jul 30 at 6:40
  • $\begingroup$ @YaniorWeg Well, for arbitrarily large examples, you can probably just take one example, and keep truncating (replacing vertices by triangles) as Santana suggested. It's easy to see the group is the same. First, there are only the obvious triangles. Now, if the original group was trivial, then the action on the triangles is trivial. Finally, it's not hard to see that the kernel is trivial, so the new group is trivial as well. $\endgroup$ – verret Jul 31 at 2:44

The paper https://arxiv.org/abs/1811.11655 claims to construct an explicit example for every even $n$ at least 12. (See Section 3.)

I don't think this paper has appeared yet, so caveat emptor.


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.