1
$\begingroup$

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?

$\endgroup$
1
  • 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$
    – Shagnik
    Commented Jul 27, 2016 at 22:01

1 Answer 1

7
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

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