How many symmetric oriented graphs with n vertices are there?

237 Views Asked by At

By a symmetric oriented graph I mean an oriented graph with non-trivial automorphisms. For the moment, I'm just considering simple graphs, rather than multigraphs.

I've tried to solve it by induction on the number of vertices, considering the connection matrix and its submatrices, but it doesn't seem to be very straightforward.

1

There are 1 best solutions below

0
On

It's easy to find at least $3^{\binom{n-1}{2}}$ symmetric oriented graphs. (For comparison, $3^{\binom{n}{2}}$ is the total number of oriented graphs on $n$ vertices.) To do so, take an arbitrary $(n-1)$-vertex oriented graph, and replace one of its vertices $v$ by two vertices $v_1, v_2$, making sure that $N^+(v_1) = N^+(v_2)$ and $N^-(v_1) = N^-(v_2)$: that the two vertices are adjacent to the same vertices of the rest of the graph in the same way.

Then there is a nontrivial automorphism swapping $v_1$ and $v_2$, so the graph is symmetric by your definition.

Oriented graphs with more interesting automorphism should be correspondingly more rare. For example, if an automorphism of our graph consists of a $k$-cycle permuting vertices $v_1, \dots, v_k$, then determining the edges incident to $v_1$ determines the edgs incident to $v_2, \dots, v_k$, giving us fewer than $3^{k-1 + \binom{n-k+1}{2}}$ such graphs. The full calculation feels tedious, and I don't want to do it, but I'm sure that the number of possible graphs decays faster than then number of possible permutations increases, as we increase the number of vertices affected.

Additionally, there should be almost no overlap between graphs symmetric under each transposition, so the total number of symmetric oriented graphs should be asymptotically around $$\binom n2 3^{\binom{n-1}{2}}.$$