An improper tournament, or tournament with ties, is a graph in which every pair of nodes is connected by a single uniquely directed edge or by a single undirected edge. There are 1, 2, and 7 improper tournaments of orders 1, 2, and 3, respectively. How many are there of order 4? Of order n?
$\begingroup$
$\endgroup$
1
asked Jul 27, 2016 at 21:16
-
1$\begingroup$ There are $3^{\binom{n}{2}}$ labelled improper tournaments, since each edge has three options. I'm pretty convinced that almost all of these should have no non-trivial automorphisms (this is true for simple graphs, and having directions should only make it harder to have an automorphism), which suggests that the number of improper tournaments on $n$ vertices up to isomorphism should be roughly $\frac{3^{\binom{n}{2}}}{n!}$. $\endgroup$– ShagnikJul 27, 2016 at 22:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
What you are looking for in the number of oriented graphs on $n$ vertices. Just think of an undirected edge in an improper tournament as a missing edge in an oriented graph and vice versa. The number of oriented graphs on $n$ vertices is OEIS A001174. Note there are $7$ oriented graphs for $n=3$ vertices (not $6$). All $7$ are shown in the first link.
You may also be interested in the paper The number of oriented graphs by Frank Harary. There are also the papers Asymptotic formulas for the number of oriented graphs and Asymptotic formulas for the number of oriented graphs (two papers both with same title).
answered Jul 27, 2016 at 22:44