4
$\begingroup$

Given a directed complete graph on $n$ vertices, is there an efficient algorithm for computing its automorphism group? Is there a nontrivial upper bound on the order of its automorphism group? How about the isomorphism of two such graphs?

$\endgroup$

2 Answers 2

6
$\begingroup$

I'm guessing that by "directed complete graph" you want each edge directed in exactly one of the two possible ways. If so, you have a tournament. Automorphism and isomorphism for tournaments is potentially easier than for general directed graphs but nobody has proved that. One thing to note is that the automorphism group has odd order and is therefore solvable, which may facilitate group-theoretic approaches.

For an upper bound on the group size, take $n!$ and remove from it the highest power of 2, but probably that is way too large. A better bound would be the answer to this stackoverflow question.

The best known algorithm needs time $n^{O(\log n)}$, which is better than the best known for general digraphs.

A paper which studies these questions is here.

$\endgroup$
0
2
$\begingroup$

As to an algorithm: There is Tarjan's algorithm for computing strongly connected components. That should certainly be a first step in every such algorithm because every automorphism will permute strongly connected components. In fact in a complete graph the components are linearly ordered so that any automorphism will in fact map all components onto themselves. Moreover: If $\Gamma = \Gamma_1 \sqcup \Gamma_2 \sqcup \ldots \sqcup \Gamma_k$ is the decomposition into components in descending order then by completeness all vertices in $\Gamma_i$ will be have an arrow pointing toward all vertices in $\Gamma_j$ if $i<j$. Therefore $Aut(\Gamma) = Aut(\Gamma_1) \times Aut(\Gamma_2) \times \ldots \times Aut(\Gamma_k)$ which reduces the problem to finding the automorphism group of a strongly connected complete graph.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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