9
$\begingroup$

I'm trying to solve two problems about graph automorphisms.

  1. I want to construct a bipartite graph without a nontrivial automorphism.
  2. I want to find the smallest possible number of nodes for a graph without a nontrivial automorphism.

For 1, I basically tried a brute-force approach: I started with two disjoint sets of nodes of unequal size and drew edges where nodes were easily exchangable. However, it didn't really work. At least for $(2,3)$-graphs I wasn't able to come up with the desired property and I have no idea how many nodes I should use. (More than the answer to problem 2 of course...) What would be a clever approach, other than try and error?

[edit] Does this one have a nontrivial automorphism?

enter image description here

For 2, I wasn't more creative than that. I tried a lot of examples to develop some intuition. I'm pretty confident that a graph without nontrivial automorphisms has to have at least $5$ nodes and I think I've found a counter-example for $6$ nodes:

enter image description here

This one has no nontrivial automorphism, right? However, I'm unsure whether there is also a counter-example for $5$ nodes and if not, how could I prove that there is none? Sadly, it's also not a bipartite graph.

$\endgroup$
10
  • 1
    $\begingroup$ The smallest graph, bipartite or not, with a trivial automorphism group has $6$ nodes. I don't have a more clever way of proving that than by exhaustion, but that would work. $\endgroup$
    – Alexander Gruber
    Jun 19, 2014 at 23:25
  • $\begingroup$ Okay, thanks, that confirms what I have so far. But how can I prove that no such graph with $5$ nodes exists? $\endgroup$
    – Amarus
    Jun 19, 2014 at 23:27
  • $\begingroup$ You're only worried about bipartite graphs, right? There are only $5$ (connected) bipartite graphs on $5$ nodes. So, you could just find those and check their automorphism groups. $\endgroup$
    – Alexander Gruber
    Jun 19, 2014 at 23:32
  • $\begingroup$ Actually, problem 2 is not only about bipartite, but general graphs. I also edited the starting post with a possible bipartite example without nontrivial automorphism that I'm not one hundred percent sure about, but I think it has none, does it? $\endgroup$
    – Amarus
    Jun 19, 2014 at 23:44
  • $\begingroup$ Easy way of proving that your six-node graph has no non-trivial automorphism: the degrees of the nodes are 4, 3, 3, 2, 1, 1 so you only have to worry about distinguishing the degree-3 nodes and the degree-1 nodes. But one of your degree-3 nodes is connected to a degree-1 node and the other one isn't; and one of your degree-1 nodes is connected to a degree-4 node while the other is connected to a degree-3 node. $\endgroup$ Jun 19, 2014 at 23:54

1 Answer 1

5
$\begingroup$

An exhaustive search (using a software package such as SAGE) would show that the smallest asymmetric graph has 6 vertices, and in fact that there is a unique asymmetric graph on 6 vertices of smallest size (the size of a graph is the number of edges). This graph is obtained by just taking a path graph on 5 vertices, and then joining the 3rd and 4th vertex of this path to a common neighbor (vertex 6). So it's a path graph with a triangle on one side of the path, making the graph asymmetric.

Simulations confirm there are a total of 8 graphs on six vertices that are asymmetric. Except for the graph mentioned in the previous paragraph, the remaining 7 graphs each have at least 7 edges.

A simple way to construct an asymmetric bipartite graph on $n$ vertices (for any $n \ge 7$) is to construct a tree, with a designated vertex as root, and with three paths of different lengths emanating from this root vertex. For example, to construct an asymmetric tree on 7 vertices, take three paths of lengths 1, 2 and 3, respectively, emanting from a vertex. Since the root is the unique vertex of degree 3 in such a graph, the root must be fixed by any automorphism. Since the paths have different lengths, the tree has no nontrivial automorphisms.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .